AcWing 102. 最佳牛围栏
原题链接
简单
作者:
Format
,
2024-04-07 20:42:56
,
所有人可见
,
阅读 7
题目描述
样例
#include <iostream>//和洛谷1419类似
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
const int N=100005;
int a[N];
int n,S,T;
bool check(double av){
double s[N];
for(int i=1;i<=n;i++){
s[i]=s[i-1]+double(a[i])-av;
}
double miv=0;
int flag=0;
for(int i=0,j=S;j<=n;i++,j++){
miv=min(miv,s[i]);
if(fabs(miv-s[i])>1e-6){
flag++;
}
if(s[j]-miv>0&&S+flag<=T) return true;
}
return false;
}
int main(){
double l=0,r=0;
cin>>n>>S;
T=n;
for(int i=1;i<=n;i++){
cin>>a[i];
r=max(r,double(a[i]));
l=min(l,double(a[i]));
}
while((r-l)>1e-5){
double mid =(l+r)/2;
if(check(mid)){
l=mid;
}else r=mid;
}
cout<<(int)(r*1000);
return 0;
}