求一个长度为 n 的序列中的一个平均值最大且长度不小于 L 的子段，输出最大平均值
最值问题可二分，从而转变为判定性问题：是否存在长度大于等于 L 且平均值大于等于 mid 的字段和
每个数与 mid 作差再转变为求非负子段
子段和问题应该利用前缀和 C，长度大于等于 L 的字段和最大值可表示为
max{Aj+1 + Aj+2 … + Ai},i-j+1-1>=L,j+1>=1
等价于
max{Ci-min{Cj}},L<=i<=n,0<=j<=i-L
注意是 i=L 时 j=0
只要 i 单调递增，j 也单调递增，可 O(1) 更新答案，然后不断二分尺取即可
j+1 的表示方法值得学习，不然推式子会习惯性把 0 的可能给忘了
不得不抱怨 POJ
浮点二分 100 次是 WA 的 50 次是 AC，哪有这种道理
只输出到个位 while(r-l>1e-5) 倒是可以，但显然精度没上面好
/*H E A D*/
int n,L;
double a[maxn],b[maxn],c[maxn];
bool C(double x){
rep(i,1,n) b[i]=a[i]-x;
rep(i,1,n) c[i]=c[i-1]+b[i];
double ans=-1e12;
double mn=1e12;
rep(i,L,n){
mn=min(mn,c[i-L]);
ans=max(ans,c[i]-mn);
}
return ans>=0;
}
int main(){
while(~iin(n)){
iin(L);
rep(i,1,n) din(a[i]);
double l=-1e6,r=1e6;
rep(i,1,50){
double mid=(l+r)/2;
if(C(mid)) l=mid;
else r=mid;
}
printf("%lld\n",(ll)(r*1000));
}
return 0;
}