AcWing 102. 最佳牛围栏
原题链接
简单
作者:
徐学神
,
2024-04-21 21:01:31
,
所有人可见
,
阅读 1
求赞!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
double l,r=2000,s[N];
ll n,f,a[N];
bool ok(double mid) {
for(ll i=1; i<=n; i++) s[i]=s[i-1]+a[i]-mid;
double mn=9e18;
for(ll i=f; i<=n; i++) {
mn=min(mn,s[i-f]);
if(s[i]-mn>=0) return 1;
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>f;
for(ll i=1; i<=n; i++) cin>>a[i];
while(r-l>1e-8) {
double mid=(l+r)/2;
if(ok(mid)) l=mid;
else r=mid;
}
cout<<ll(r*1000);
return 0;
}