题目描述
注释给出了部分解释。
C++ 代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1e5+10;
const double eps=1e-8;
double a[N];
double sum[N];
int n,m;
bool check(double mid)
{
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i]-mid; //所有值减取平均值,就可以和特殊值0进行比较,方便后面操作和思考。
}
double mins=0; //用mins来维护减去部分的最小值
for(int k=m;k<=n;k++)
{
mins=min(mins,sum[k-m]);
if(sum[k]>=mins) return true; //如果sum[k]>=mins,说明当前mid符合条件
}
return false;
}
int main()
{
cin>>n>>m;
double maxn;
for(int i=1;i<=n;i++)
{
scanf("%lf",&a[i]);
maxn=max(maxn,a[i]); //动态维护前缀序列(目的是为了方便和0比较),所以sum不写在这里,写在chec那里
}
double l=1,r=maxn;
while(r-l>eps)
{
double mid=(r+l)/2;
if(check(mid)) l=mid;
else r=mid;
}
cout<<(int)(r*1000)<<endl; //要求下取整,所以取r。
return 0;
}