链接：https://ac.nowcoder.com/acm/problem/231037
来源：牛客网

题目描述

钢哥把他的的鱼塘分割成 N 个水池，每个里都有一定数量的鱼，其数量不会少于 1 条，也不会超过 500 条。

钢哥希望用围栏将一部分连续的水池围起来，并使得围起来的区域内每个水池包含的鱼的数量的平均值达到最大。

围起区域内至少需要包含 M 个水池，其中 M 会在输入中给出。

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

输入描述: 

第一行输入整数 N 和 M，数据间用空格隔开。（1≤N≤100000， 1≤M≤N）
接下来 N 行，每行输入一个整数，第 i+1 行输入的整数代表第 i 片区域内包含的鱼的数目。

输出描述: 

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

输入 

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

输出 

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

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

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

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

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

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

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

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

using namespace std;

const int N = 100005;
int g[N];
double sum[N];

int n, m;

bool check(double avg) {
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + g[i] - avg;
    }

    double minn = 0;
    for (int i = 0, j = m; j <= n; j++, i++) {
        minn = min(minn, sum[i]);
        if(sum[j] - minn >= 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", &g[i]);
        r = max(r, (double)g[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; 
}