首先来首歌曲来放松一下吧！

题目链接：102. 最佳牛围栏

题目背景：

一道难题，前缀和，差分，双指针的叠加应用！

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤N≤100000
1≤F≤N

输入样例：

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

输出样例：

1
6500

题目分析：

题目要求：

给了N块地，每块地有一些牛，现在想让你在1 ~ N 块地里，连续的选取大于 f 块地，使得得到的平均数最大！

输出最大的平均值！

解题思路：

首先说一下我的思路：（TLE）

因为数据是10的五次方，我用的是O(N)的做法，那就是10的10次方了，远远大于C++一秒可以计算的次数了！

我就是暴力找一遍！

先计算前缀和，为了以后用的时候方便！然后用两重for循环去找，一个在区间左端点，一个在右端点，为了保证区间长度大于f，如解法一的两重for 循环的循环变量设置！每次取一个最大值即可，当然，它超时了！

现在开始正确的O(NlogN)的做法：

二分思想：

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

就是说最终的答案那个平均值，一定在1 ~ 2000头牛之间，我们用二分，从mid开始，如果发现mid是可以合法的，那么一定有大于mid的平均值可以作为最后答案，也就是一定有一个从mid开始的一个长度>=f的区间可以达到更大的平均值！所以区间开始一步步缩小，为了达到乘1000向下取值，精度就得达到1e-4左右，为了保险将精度压到1e-5！

在平均值check时，可以将原值都减去传入的二分平均值mid，最后再进行前缀和！这时看一个区间平均值就可以直接看前缀和是不是大于0，大于0则平均值大于mid，反之，小于mid！

如果可选区间有一个大于mid的区间，那么，最终答案一定大于mid，在主函数内部进行二分区间的缩小，往后移动即可！

此处有一个即可，有一个，只要有就行，只要有就可以使得mid成立，即最终结果一定比mid大，区间要后移！有就行，那么当然要选择最小的，sum[j] - minv >= 0 要想使这个式子成立，只要使得minv为可选区间最小即可，只要成立一种就行，用最小的岂不是更方便！

接下来就是区间的变化，i,j始终保持f的距离！然后sum[j] - minv >= 0 可以看到这个区间的长度一定是大于f的，可以画个图去理解！

可以结合下面某位大神的题解：

我们要找的是 有没有一段不小于F的区间，使这段区间的平均数尽可能的大，**如果我们找到了一段连续的区间且区间长度不小于F且平均数大于我们二分的平均数 ，**那么大于这个数的区间也一定满足了， 我们直接返回true！

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

我们还可以继续优化，因为我们不仅需要找F大小区间内，我们还要找＞F大小区间内的，我们如果用二次for太费时间了，我们这里可以使用双指针的做法，我们设i=0,j=F ，每次使两个数++ ，因为i,j始终满足相距F的距离，所以我们用一个变量minv来存储i所遍历到的最小值，这样我们比较的距离一定是≥F的，并且如果我们用j位的前缀和数减去minv的话，就能得到我们的最优解，如果这个最优解＞= 0 那么就满足我们的指定条件，即可以得到平均值大于min的取值，返回true！

yxc大神的视频讲解：点击这里！

一篇好理解一点的题解：点击这里！

题解：

解法一：本人的暴力超时做法！（TLE）

时间复杂度：O(N2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>

using namespace std;

const int N = 100010;
int g[N], n, f;

int main()
{
    cin >> n >> f;
    for(int i = 1; i <= n; i++)
    {
        cin >> g[i];
        g[i] += g[i - 1];
    }
    
    double res = 0;
    for(int r = f; r <= n; r++)
    {
        for(int l = 1; l <= r - f + 1; l++)
        {
            double t = (g[r] - g[l - 1])/(r - l + 1.0);
            res = max(res, t);
        }
    }
    res *= 1000;
    printf("%.0lf\n", res);
    return 0;
}

解法二：使用二分，前缀和，双指针的yxc大神的AC做法！

好好看看代码，可以结合上面的题解与上面附出的大神的视频！

注意：r 要取最大牛，输入时用来max函数，其实不取最大值，直接带入2000也可以，但取最大值更加精准！

可能的最大值 ：题目最后这样写的！即要输出极大值，很明显r 最终一定比l大，所以最后要输出 r , 而不是 l ，输出 l 的话，其值一定会比 r 小！

这里sum数组的变化是不需要处理的，数组每次其实都是重新复制去覆盖的，不用担心上一下会影响到下一次！

cow[i] - avg：可以看成整体，将每一位数都减去平均值！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>

using namespace std;

const int N = 100010;
int cow[N];
double sum[N]; 
int n, f;

bool check(double avg)
{
    for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + cow[i] - avg;
    
    double minv = 0;
    for(int i = 0, j = f; j <= n; i++, j++)
    {
        minv = min(minv, sum[i]);
        if(sum[j] - minv >= 0) return true;
    }
    return false;
}

int main()
{
    cin >> n >> f;
    
    double l = 0, r = 0;
    for(int i = 1; i <= n; i++) cin >> cow[i], r = max(r, (double)cow[i]);
    
    while(r - l > 1e-5)
    {
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    
    cout << int(r * 1000) << endl;
    return 0;
}