二分答案,判定“是否存在一个长度不小于L的字段,平均数不小于二分的值”,如果把数列中的每个数都减去二分的值，就转换成是否存在一个长度不小于L的字段，字段和非负。

字段和可以转化为前缀和相减的形式,即sum[i]表示A[1]~A[i]的和，则有:

$$(i - j >= L)max(A[j + 1] + A[j + 2] + ... + A[i]) = $$$$max(sum[i](L <= i <= n) - min(sum[j])(0 <= j <= i - L)) $$

仔细观察上面的式子可以发现，随着i的增大,j的取值范围0~i - L每次只会增大1。换言之,每次只会有一个的新的取值进入min{sum[j]}的候选集合，所以我们没有必要每次循环枚举j，只需要用一个变量记录当前的最小值，每次与新的取值sum[i - L]取min就可以了

for (int i = F; i <= N; ++i) {
	minval = min(minval, sum[i - F]);
	ans = max(ans, sum[i] - minval);
}

解决这个问题之后,我们只需看一下最大字段和是不是非负数，就可以确定二分的变化范围了。 AC代码：

#include <bits/stdc++.h>
using namespace std;
int N, F;
double a[100001], b[100001], sum[100001];
double eps = 1e-5;
int main() {
	scanf("%d%d", &N, &F);
	for (int i = 1; i <= N; ++i)
		scanf("%lf", &a[i]);
	double L = -1e6, R = 1e6;
	while (R - L > eps) {
		double mid = (R + L) / 2, minval = 1e6, ans = -1e6;
		for (int i = 1; i <= N; ++i)
			b[i] = a[i] - mid; 
		for (int i = 1; i <= N; ++i)
			sum[i] = sum[i - 1] + b[i];
		for (int i = F; i <= N; ++i) {
			minval = min(minval, sum[i - F]);
			ans = max(ans, sum[i] - minval);
		}
		if (ans >= 0)
			L = mid;
		else
			R = mid;
	}
	printf("%d\n", (int)(R * 1000));
	return 0;
}