AcWing-102-最佳牛围栏

问题

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤N≤100000,
1≤F≤N

输入样例：

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

输出样例：

6500

思路

题目大意是：给定一个正整数列A，求一个平均数最大的、长度不小于F的（连续的）子段。

• 朴素算法

首先用传统的算法思路，先求出a数组（依次存放每块农田牛的数量）的前缀和s，去枚举每个左端点和右端点（下标至少相差F-1），每次枚举，将该子段的平均值保存下来，遍历完成后输出最大平均值即可，如下公式。其时间复杂度为$O(N^2)$，造成超时。

$ans = \max_{1\le i \le N-F+1,i+F-1\le j \le N}\{(s[j]-s[i-1])/(j-i+1)\}$

• 二分查找

其次，想到二分，由题，每块农田的牛的数量处于[1,2000]区间中，则其平均值也处于该区间中。
直接二分平均值即可，l=1，r=2000 ，mid即为当前的平均值，如果数列a减去mid后的子段（需满足长度大于等于F）中存在一个子段和大于等于0的子段，即证明当前mid小于等于目标平均值，目标值应该在[mid,r]区间中。否则，证明当前mid大于了目标平均值，目标值应该在[l,mid]中。

题解

题解一（TLE超时）

#include<iostream>
#include<cstdio>

using namespace std;

const int MAX = 100010;
int N, F;
int a[MAX];
int s[MAX];

int main() {
    cin >> N >> F;
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }

    double res = 0;
    for (int i = 1; i <= N - F + 1; ++i) {
        for (int j = i + F - 1; j <= N; ++j) {
            int sum = s[j] - s[i - 1];
            res = max(res, sum * 1.0 / (j - i + 1));
        }
    }

    cout << int(res * 1000) << endl;

    return 0;
}

题解二（AC）

#include<iostream>
#include<cstdio>

using namespace std;

const int MAX = 100010;
int N, F;
double a[MAX], s[MAX];

// 判断在平均值为Avg的情况下，将子段减去avg后，
// 是否存在子段使其字段和大于等于0且其长度大于等于F
bool calc(double avg) {
    for (int i = 1; i <= N; ++i) s[i] = s[i - 1] + a[i] - avg;

    double min_val = 1e9;
    for (int i = F; i <= N; ++i) {
        min_val = min(min_val, s[i - F]);
        if (s[i] >= min_val) return true;
    }

    return false;
}

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

    double l = 1, r = 2000; //最小平均为1，最大平均为2000
    while (l + 1e-5 < r) {
        double mid = (l + r) / 2;
        if (calc(mid)) l = mid;
        else r = mid;
    }

    cout << int(r * 1000) << endl;

    return 0;
}