最大均值
Description–
解题思路–
二分答案
把所选子串每个数减去mid,若子串和仍为正数,则该子串的平均值大于mid
代码–
#include <iostream>
#include <cstdio>
#include <cmath>
#define db double
using namespace std;
const db eps = 1e-5;
db l, r, a[100005], s[100005];
int n, ll;
bool check(db k)
{
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i] - k;
db minn = 1e10, maxx = -1e10;
for (int i = ll; i <= n; ++i)
{
minn = min(minn, s[i - ll]);
maxx = max(maxx, s[i] - minn);
}
return maxx >= 0;
}
int main()
{
scanf("%d%d", &n, &ll);
l = 1e10;
for (int i = 1; i <= n; ++i)
{
scanf("%lf", &a[i]);
l = min(l, a[i]), r = max(r, a[i]);
}
while (l + eps < r)
{
db mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%d", (int)floor(r * 1000));
return 0;
}