问题 K: 计算平均值最大子段
可以想到的做法是先枚举区间长度，然后计算每一个符合的区间平均值，但是会超时（timeout），很明显是时间复杂度n^2
考虑如何优化（当然一开始没想到，还是老师提醒了一波)(明明之前课上还做到过）（哭）
如何在O(n)判断一个区间是否满足，除了前缀和加除法的方法，也可以将数组的所有元素减去平均值再做前缀和,这样如果区间大于等于0那么就是满足的，相当于式子转化一下((a+b+c)/len=avg => a+b+c=len*avg)
这样我们就可以贪心的想，最大值-最小值>=0，且保证两则距离大于等于L，这样即可在O(n)下完成
下面是实现过程：
先让区间[l,r]（保证r-l>=L）右移，维护[0,l-1]的最小值，对于每个r,如果pre[r]-mn>=0则满足
点击查看代码
int n,L;
double a[N],pre[N];
bool check(double x){
for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i]-x;//将求平均值直接转化为前缀和
double mn=1e9;
for(int i=L,j=0;i<=n;i++,j++){
mn=min(mn,pre[j]);//取区间外前缀的最小值
if(pre[i]-mn>=0) return true;//枚举每个符合的i
}
return false;
}
void bu_f(){
n=read(),L=read();
for(int i=1;i<=n;i++) cin>>a[i];
double l=0,r=3000;
while(r-l>1e-5){
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
cout<<(int)(r*1000);//注意输出，向上取整直接取r即可
}