AcWing 102. 最佳牛围栏
原题链接
简单
作者:
啥也不会hh
,
2022-06-24 09:08:36
,
所有人可见
,
阅读 168
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 100010;
int n, f;
double s[N], a[N];
bool check(double avg)
{
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i] - avg;
double mins = 0;
for (int k = f; k <= n; k ++ )
{
mins = min(s[k - f], mins);
if (s[k] >= mins) return true;
}
return false;
}
int main()
{
cin >> n >> f;
double l = 0, r = 0;
for (int i = 1; i <= n; i ++ )
{
scanf("%lf", &a[i]);
r = max(r, a[i]);
}
while (r - l > 1e-5)
{
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%d", (int)(r * 1000));
return 0;
}