AcWing 102. 最佳牛围栏
原题链接
简单
作者:
geats兔
,
2024-03-02 01:11:36
,
所有人可见
,
阅读 20
************* 算法: 浮点数二分+前缀和**************_**
#include<iostream>
using namespace std;
const int N=100010,INF=1e9;
int a[N];
double s[N];
int n,f;
bool check(double avg){
for(int i=0;i<=n;i++) s[i]=s[i-1]+a[i]-avg;
double minv=INF;
for(int k=f;k<=n;k++)
{
minv=min(minv,s[k-f]);
if(s[k]>=minv) return true;
}
return false;
}
int main(){
cin>>n>>f;
for(int i=1;i<=n;i++)
cin>>a[i];
double l=1,r=2000;
while(r-l>1e-5){
double mid=l+(r-l)/2;
if(check(mid)) l=mid;
else r=mid;
}
cout<<(int)(r*1000)<<endl;
return 0;
}