AcWing 102. 最佳牛围栏
原题链接
简单
作者:
tyro_520
,
2024-01-24 16:10:15
,
所有人可见
,
阅读 38
C++ 代码
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cout.tie(0);cin.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> pLL;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
const int MOD = 1e9 + 10;
double a[N],s[N];
int n,F;
bool check(double x){
for(int i = 1;i <= n;i++)
s[i] = s[i-1] + a[i] - x; //问题转化
double minn = inf;
for(int k = F;k <= n;k++){
minn = min(minn,s[k-F]);
if(s[k] >= minn) return true;
}
return false;
}
int main()
{
ios;
cin >> n >> F;
double l = 0,r = 0;
for(int i = 1;i <= n;i++){
cin >> a[i];
r = max(r,a[i]);
}
while(r - l > 1e-7){
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
int ans = r * 1000; //这里是下去整,如果去l会出现错误,因为 r > l!
cout << ans << endl;
return 0;
}