P1404 平均数
求最大平均数子串，考虑分数规划。
设当前有 $k$ 个数，第 $i$ 个数的值为 $w _ i$ ，当前二分值为 $x$ ，则
$$
\begin{aligned}
& \frac {\sum _ {i = 1} ^ k w _ i} k \ge x \\
\Longrightarrow & \sum _ {i = 1} ^ k w _ i \ge x k \\
\Longrightarrow & \sum _ {i = 1} ^ k w _ i - x \ge 0
\end{aligned}
$$
这道题还有一个要求，长度要大于等于 $m$ ，如果直接枚举子串的起始位置复杂度就已经是 $O(n ^ 2$ 了，这是不能接受的。考虑如何优化。我们将当前的 $w _ i - x$ 做前缀和，同时维护一个最小前缀和，如果当前的前缀和减去最小前缀和大于等于 $0$ ，即中间的一段就大于等于 $0$ 。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
const double eps = 1e-5;
int n, m;
double A[N], s[N];
bool check (double x)
{
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + A[i] - x;
double mn = 0;
for (int i = m; i <= n; i++)
{
mn = min(mn, s[i - m]);
if (s[i] >= mn)
return true;
}
return false;
}
int main ()
{
cin >> n >> m;
double l = 0, r = 0, mid;
for (int i = 1; i <= n; i++)
{
cin >> A[i];
r = max(r, A[i]);
}
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid))
l = mid;
else
r = mid;
}
cout << (int)(r * 1000);
return 0;
}
|