/*
遇到求最值，且答案显然具有单调性，即可用二分答案进行判定
那么本题要求最大的平均数，就可以转换成是否存在一个平均数为mid的段
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 100005
#define esp 1e-6
int N,L;
double a[maxn],b[maxn],sum[maxn];
int judge(
double m){
double tmp=-1e10,Min=
1e10;
for(
int i=
1;i<=N;i++)b[i]=a[i]-
m;
for(
int i=
1;i<=N;i++)sum[i]=sum[i-
1]+
b[i];
for(
int i=L;i<=N;i++
){
Min=min(Min,sum[i-
L]);
tmp=max(tmp,sum[i]-
Min);
}
if(tmp>=
0)
return 1;
return 0;
}
int main(){
scanf("%d%d",&N,&
L);
for(
int i=
1;i<=N;i++) scanf(
"%lf",&
a[i]);
double l=-1e6,r=
1e6,mid,ans;
while(r-l>
esp){
mid=(l+r)/
2;
if(judge(mid))
//存在某一段平均数大于等于mid
l=
mid;
else r=
mid;
}
printf("%d\n",
int(r*
1000));
}
转载于:https://www.cnblogs.com/zsben991126/p/10245642.html
