题目要求最大的平均值,直接求不好求,因此可以使用二分答案。
二分出一个平均值avg,判断是否存在方案使得平均值大于avg,若存在,l=avg,否则r=avg,最后输出r(例如l=6.4999…,r=6.5,则输出l会导致答案变为6499,错误)。
考虑如何判断,若将原序列的每一项减去avg,则只需求出一段大于f的序列使得和大于等于0即可,设这段序列左端点为i,右端点为k,对于每个k,只需求出满足s[k]-s[i-1]最大的i即可,因此需要找出最小的s[i-1]。因为i=1 ~ k-f+1,所以i-1=0 ~ k-f,也就是找出s[0~k-f]的最小值,因此可以从前往后遍历,从f开始,遍历到x时记录最小值mins=min(mins,s[x-f]),若s[x]-mins大于0,则表示存在满足当前avg的方案,返回true即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,f;
double a[N],s[N];
double check(double avg){
for(int i=1;i<=n;i++){
s[i]=s[i-1]+a[i]-avg;
}
double mins=0;
for(int k=f;k<=n;k++){
mins=min(mins,s[k-f]);
if(s[k]>=mins)return true;
}
return false;
}
int main(){
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-5){
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
cout << (int)(r*1000) << endl;
return 0;
}