<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

$1 \\le N \\le 100000$
$1 \\le F \\le N$

输入样例：

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

输出样例：

6500

思路

二分最难的地方就在于$check$函数的写法，我们先来捋一遍思路，防止写代码的时候思路混乱

1. 我们要找的是 有没有一段不小于F的区间，使这段区间的平均数尽可能的大，如果我们找到了一段连续的区间且区间长度不小于F且平均数大于我们二分的平均数 那么大于这个数且区间也满足的一定满足了 我们直接判断正确即可

2. 因为我们要找一段区间的平均数，根据平均数的一个基本应用，显而易见，对于一段序列，每个数减去我们所算的平均数，如果大于0 那么他本身就大于平均数，如果小于0 那么它本身就小于平均数 此时我们就能算出哪些数大于0 哪些数小于0 ，之后我们再使用前缀和，就能判断一个区间内的平均值是否大于或小于我们二分的平均数了

3. 据2.我们还可以继续优化，因为我们不仅需要找$F$大小区间内，我们还要找$>F$大小区间内的，我们如果用二次for太费时间了，我们这里可以使用双指针的做法，我们设$i=0,j=F$ 每次使两个数$++$ 因为i,ji,j始终满足相距FF的距离，所以我们用一个变量$minv$来存储ii所遍历到的最小值，这样我们比较的距离一定是$\ge F$的，并且如果我们用jj位的前缀和数减去$minv$的话，就能得到我们的最优解，如果这个最优解$\ge 0$ 那么就满足我们的指定条件（如果不懂这一步 请看②）。 到此，结束。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
const double EPS = 1e-5;
int n,m;
int cow[N];
double sum[N];
bool check (double x) {
    for (int i = 1;i <= n;i++) sum[i] = sum[i - 1] + (cow[i] - x);
    double minv = 0;
    for (int i = 0,j = m;j <= n;i++,j++) {
        minv = min (minv,sum[i]);
        if (sum[j] - minv >= 0) return true;
    }
    return false;
}
int main () {
    scanf ("%d%d",&n,&m);
    double l = 0,r = 0;
    for (int i = 1;i <= n;i++) {
        scanf ("%d",&cow[i]);
        r = max (r,(double)cow[i]);
    }
    while (r - l > EPS) {
        double mid = (l + r) / 2;
        if (check (mid)) l = mid;
        else r = mid;
    }
    printf ("%d",(int)(r * 1000));
    return 0;
}