【NOIP2015模拟10.20】平均数

这题不可贪心，只能二分+前缀和判。
上标：

#include<cstdio>
#include<algorithm>
#define N 300010
#define db double
using namespace std;
int n,K,a[N];
db l,r,mid,mi,b[N];
bool bz;

inline int read()
{
	int x=0; char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}

int main()
{
	freopen("average.in","r",stdin);
	freopen("average.out","w",stdout);
	n=read(),K=read();
	for(int i=1;i<=n;i++) a[i]=read();
	l=0,r=1000000;b[0]=0;
	while (l+0.0001<r)
	{
		mid=(l+r)/2.0;
		for (int i=1;i<=n;i++)
			b[i]=b[i-1]+a[i]-mid;
		bz=0;mi=0;
		for (int i=K;i<=n;i++)
		{
			if (b[i]-mi>=-0.0001) {bz=1; break;}
			mi=std::min(mi,b[i-K+1]);
		}
		if (bz) l=mid; else r=mid;
	}
	printf("%.10lf
",l);
	return 0;
}