AcWing 102. 最佳牛围栏
原题链接
简单
1.最佳牛围栏
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int cow[N];
double sum[N];
int n,m;
bool check(double avg)
{
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+cow[i]-avg; //先求一下前缀和
double minv=0;
for(int i=0,j=m;j<=n;i++,j++)
{
minv=min(minv,sum[i]);
if(sum[j]>=minv)
return true;
}
return false;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>cow[i];
double l=0,r=2000;
while(r-l>1e-5)
{
double mid=(r+l)/2;
if(check(mid))
l=mid;
else
r=mid;
}
printf("%d\n",int(r*1000));
return 0;
}