最大均值 / Best Cow Fences

题目链接：ybt高效进阶1-3-3 / POJ 2018

题目大意

求一个序列里面平均值最大的，长度不小于 L 的连续字段。
输出最大的平均值乘 1000 向下取整的东西。

思路

这道题很明显是二分平均值。

那我们可以把序列里的每个数都减平均值，那问题就变成了要找长度不小于 L 的字段使字段和大于等于 $0$。

那这个我们可以用前缀和维护，并且记录 $1\sim i-L$ 这个区间里面每个位置前缀和里的最小值，然后用当前的值减去这个最小值，就可以得到以这个结尾的，长度不小于 L 的平均值最大的廉租字段的平均值了。

那我们就可以通过这个方法得出答案。

代码

#include<cstdio>
#include<iostream>

using namespace std;

int n, L, a[100001];
double now[100001], answer, minn, sum[100001], l, r, mid;

bool check(double mid) {
	for (int i = 1; i <= n; i++) {
		now[i] = 1.0 * a[i] - mid;
	}
	
	for (int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1] + now[i];
	}
	minn = 1e9;
	answer = -1e9;
	for (int i = L; i <= n; i++) {
		minn = min(minn, sum[i - L]);
		answer = max(answer, sum[i] - minn);
	}
	
	return answer >= 0;
}

int main() {
	scanf("%d %d", &n, &L);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	
	l = -1e6;
	r = 1e6;
	while (r - l > 1e-5) {
		mid = (l + r) / 2;
		if (check(mid)) l = mid;
			else r = mid;
	}
	
	printf("%d", int(r * 1000));
	
	return 0;
}