题目描述

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

为求出一段大于Fd区间平均值最大，我们可是使用前缀和与二分的做法，怎么做呢？

定义double类型的数l, r，其中r为所有区间最大的那个数，求平均值不可能大过它，l = 0，取中值mid代入到check函数。

这里check函数是什么呢？， 定义前缀和s[N],数组，将原数组a[N]中的每个数都减去mid, 找出大于F长度的一段，判断是否大于0，若存在这么一段，那么之一段的平均值是大于mid的，返回true，回到二分中l = mid, 反之 r = mid;

最终得出r，根据题目要求乘以1000输出

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, F;
double a[N], s[N];

bool check(double avg)
{
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i] - avg;

    double mins = 0;
    for (int i = F; i <= n; i ++ )
    {
        mins = min(mins, s[i - F]);
        if (s[i] - mins >= 0) return true;
    }
    return false;
}

int main()
{
    cin >> n >> F;
    double r = 0;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lf", &a[i]);
        r = max(r, a[i]);
    }

    double l = 0;
    while (r - l > 1e-5)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%d", (int)(r * 1000));
}