AcWing 102. 最佳牛围栏
原题链接
简单
作者:
乡村守望者
,
2020-02-17 13:59:41
,
所有人可见
,
阅读 630
//二分答案区间 1-2000
//每次check
//check 动态规划思想
//以k为右端点的区间最大值平均值是否大于等于参数
//处理第四步时 可以每次让减去参数,再看区间有无大于0
#include<iostream>
using namespace std;
const int N = 100010;
int n,f;
double a[N];
double s[N];
bool check(double avg)
{
for(int i=1;i<=n;++i)s[i]=s[i-1]+a[i]-avg;
double mins = 10000;
for(int i=f;i<=n;++i){
//前缀和数组
mins = min(s[i-f],mins);
if(s[i]>=mins)return true;
}
return false;
}
int main()
{
cin>>n>>f;
for(int i=1;i<=n;++i)cin>>a[i];
double l = 1,r = 2000;
//保留三位 就取1e-5
while(r-l>1e-5)
{
//不能l+r>>1
double mid = (l+r)/2;
//若找得到 说明答案可以更大
if(check(mid))l = mid;
else r=mid;
}
//printf("%.0lf",r*1000); 不行 这是四舍五入 而不是下取整
printf("%d\n",(int)(r*1000));//强转int是截断法 是下取整
return 0;
}