二分法前缀和：最佳牛围栏

前缀和：最佳牛围栏"/>

二分法前缀和：最佳牛围栏

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

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

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

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

输入格式

第一行输入整数 NN 和 FF，数据间用空格隔开。

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

输出格式

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

数据范围

1≤N≤1000001≤N≤100000
1≤F≤N1≤F≤N

输入样例：

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

输出样例：

6500

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int cows[N]; double sum[N];int n, m;bool check(double avg)
{for (int i = 1; i <= n; i++){sum[i] = sum[i - 1] + cows[i] - avg;//前缀和}double minv = 0;for (int i = 0, j = m; j <= n; j++, i++){minv = min(minv, sum[i]);if(sum[j] - minv >= 0)return true;}return false;
}int main() {cin>>n>>m;double l = 0, r = 0;for (int i = 1; i <= n; i++){cin>>cows[i];r = max(r, (double)cows[i]);}while(r - l > 1e-5)//运用二分法来遍历出最大的avg（平均值） {double mid = (l + r) / 2;if(check(mid))l = mid;else r = mid;}cout<<(int)(r * 1000);return 0;
}