依然是学习分析方法的一道题

求一个长度为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;

}