AcWing 102. 最佳牛围栏
原题链接
简单
作者:
西世残圣
,
2021-06-06 16:22:47
,
所有人可见
,
阅读 243
#include<bits/stdc++.h>//给大佬们的题解稍微改编一下加个注释OvO
using namespace std;
const int N=1e5+10;
double a[N],s[N],ans,minx;
int n,k;
int check(double mid)
{//把每个区间减去平均值后的数加起来如果大于零,这个平均值就符合
for(int i=1;i<=n;i++)s[i]=a[i]-mid,s[i]+=s[i-1];//mid为我们算出的平均值
ans=-1e8,minx=1e8;
for(int i=k;i<=n;i++){//模拟一个区间
minx=min(minx,s[i-k]);//左面的值越小越好
ans=max(ans,s[i]-minx);//枚举每个区间看能否大于零,即平均值存在
}
return ans>0;//如果存在平均值为mid的一段区间,就返回成功
}
void solve(double l,double r)
{
while(l+1e-5<r)
{
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
cout<<(int)(r*1000)<<endl;;//尝试r或者l
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
solve(1,2000);//平均值的范围题目给的1到2000即可
return 0;
}