最佳牛围栏

农夫约翰的农场由 $N$ 块田地组成，每块地里都有一定数量的牛，其数量不会少于 $1$ 头，也不会超过 $2000$ 头。

约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。

围起区域内至少需要包含 $F$ 块地，其中 $F$ 会在输入中给出。

在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入格式

第一行输入整数 $N$ 和 $F$，数据间用空格隔开。

接下来 $N$ 行，每行输入一个整数，第 $i+1$ 行输入的整数代表第 $i$ 片区域内包含的牛的数目。

输出格式

输出一个整数，表示平均值的最大值乘以 $1000$ 再 向下取整 之后得到的结果。

数据范围

$1≤N≤100000$
$1≤F≤N$

输入样例

10 6
6 
4
2
10
3
8
5
9
4
1

输出样例

6500

解析

① 可能的最大值，抓住关键词，考虑是否可以用二分，假设存在某一个平均值满足题目条件，那么小于该值的平均值一定能满足题目条件，而大于该值的平均值不一定能满足题目条件，于是可得 可以用二分

② 为了快速判断某一区间的值是否大于我们二分的平均值，我们可以让每个数减去平均值，这样再将它们全部加起来就可以判断当前某一区间的平均值是否大于二分的平均值。

最后看代码

#include <cstdio>
#include <cstring>
#include <iostream>
//前排提醒 更简单的可以看Yxc的代码
const int N = 100005;
int arr[N];
double f[N];

int n, F;

bool cheak(double x) {
	for (int i = 1; i <= n; i++) { //这里是②的实现
		f[i] = f[i - 1] + arr[i] - x;
	}
	
	double minv = 1e9; //因为保证至少包含 F 块地，所以可以有F + 1， F + 2块，我们选个最优的即可
	for (int i = 0, j = F; j <= n; i++, j++) { //用双指针保证每次都是 F 块 用minv保证最小的是最优的
		minv = std::min(minv, f[i]);
		if(f[j] - minv > 0) return true;
	} return false;
}

int main() {
	scanf("%d %d", &n, &F);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
	}
	
	double l = 0, r = 100000; //二分
	while(r - l > 1e-5) {
		double mid = (l + r) / 2;
		if(cheak(mid)) l = mid;
		else r = mid;
	}
	
	printf("%d\n", (int)(r * 1000));
	return 0;
}