博客地址 Nicoppa的个人博客
不懂吗？那就搞懂为止

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

题目题解

先分析这道题应该用什么算法，本题应该怎么入手

首先本题没有出现二分的特征词：“最大值最小” or “最小值最大” 并且给的数列不具备单调性，并且不适于排序，我们看到这种题可以先提出假设 比如，假设这道题用二分能解出

那么我们判断是否存在一个平均值大于等于mid，如果最优解是x，那么mid <= x的时候，必然可以找到一段，其平均值≥mid， 否则 一定找不到

对于二分，二分是二分性而不是单调性 只要满足可以找到一个值一半满足一半不满足即可 而不用满足单调性

那么这个题我们就可以使用二分来解决

知道了这道题的算法之后，我们就来分析这道题

首先我们二分针对的是平均数，那么根据我们就可以捏出以下主函数

int main() {
    scanf("%d %d", &n, &m);
    double l = 0, r = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &cows[i]);
        r = std::max(r, (double)cows[i]);
    } //最小左区间 最大右区间

    while(r - l > 1e-5) { //开始二分 因为是实数所以这里还搞个精度
        double mid = (l + r) / 2; // 不是>>1 这里是实数
        if(check(mid)) l = mid; //将问题转变为判定问题
        else r = mid;
    } printf("%d\n", (int)(r * 1000)); //因为我们找的极大值 所以要右端点*1000 否则可能会出错
    return 0; 
}

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

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

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

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

我们便可以写出二分的$check$代码

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 = std::min(minv, sum[i]); //找最优极小值
        if(sum[j] - minv >= 0) return true; //进行判断
    } return false; //如果所有的都不满足，那么这个平均数就一定不满足
}

以下是全代码：

//#define fre yes

#include <cstdio>
#include <iostream>

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 = std::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", &cows[i]);
        r = std::max(r, (double)cows[i]);
    }

    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; 
}