AcWing 102. 最佳牛围栏
原题链接
简单
作者:
代码人生
,
2022-09-12 13:34:52
,
所有人可见
,
阅读 127
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,f;
int a[N];
double sum[N];
bool check(double avg){
for(int i=1;i<=n;i++) sum[i] = sum[i - 1] + a[i] - avg;
double minv = 0;
for(int i=0,j=f;j<=n;i++,j++){
minv = min(minv,sum[i]);
if(sum[j] >= minv) return true;
}
return false;
}
int main(){
scanf("%d %d",&n,&f);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
double l = 0,r = 2000;
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;
}