USACO 最佳牛围栏 （二分答案+前缀和+双指针）

题面

农夫约翰的农场由 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

思路

暴力枚举n方，本题数据量十万，直接炸裂。果断二分答案，二分了答案之后我们考虑如何写判定函数。因为我们二分的是平均值，那么这里有一个小技巧，就是拿所有元素的值减去平均值。然后我们要求的是某段长度大于m区间，那么我们对这个数组施加前缀和操作，最后双指针扫描一遍数组，取出最长的那段判断。

代码实现

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
using namespace std;
typedef long long ll;
const int maxn=100010;
int n,m;
double sum[maxn];
int a[maxn];
bool check (double mid) {
    for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]-mid;
    double minv=0;
    for (int i=0,j=m;j<=n;i++,i++) {
        minv=min (minv,sum[i]);
        if (sum[j]>=minv) return true;
    }
    return false;
}
int main () {
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    double l=0,r=2000;
    while (r-l>1e-5) {
        double mid=(l+r)/2;
        if (check (mid)) l=mid;
        else r=mid;
    }
    printf ("%d\n",(int ) (r*1000));
    return 0;
}