AcWing 102. 最佳牛围栏
原题链接
简单
作者:
Aleia
,
2024-10-08 20:29:31
,
所有人可见
,
阅读 1
#include <iostream>
using namespace std;
const int N = 1e6+10;
double a[N];
double sum[N];
int main()
{
int N,L;
cin>>N>>L;
for(int i=1;i<=N;i++) cin>>a[i];
double l = 1,r = 2000;
while(r-l>1e-5)//r>l
{
double mid = (l+r)/2;
for(int i=1;i<=N;i++) sum[i] = sum[i-1] + a[i] - mid;//前缀和,将avg>=mid ,转换为avg - mid >=0
double ans = -1e10;
double min_val = 1e10;
for(int i=L;i<=N;i++)
{
min_val = min(min_val,sum[i-L]);
ans = max(ans,sum[i] - min_val);
}
if(ans>=0) l = mid;
else r= mid;
}
cout<<int(r*1000)<<endl;
return 0;
}