AcWing102. 最佳牛围栏

题目

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

• $1\le N\le 100000$
• $1\le F\le N$

输入样例

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

输出样例

6500
1

分析

题意简而言之就是：给定正整数序列 $A$，求一个平均数最大的、长度不小于 $L$ 的（连续的）子段。

二分答案，判定 “是否存在一个长度不小于 $L$ 的子段，平均数不小于二分的值”。

如果把数列中每个数都减去二分的值，就转化为判定 “是否存在一个长度不小于 $L$ 的子段，子段和非负”。

下面着重来解决以下两个问题。

1、求一个子段，它的和最大，没有 “长度不小于 $L$” 这个限制。

无长度限制的最大子段和问题是一个经典问题，只需 $O(N)$ 扫描该数列，不断把新的数加入子段，当子段和变成负数时，把当前的整个子段清空。扫描过程中出现过的最大子段和即为所求。POJ-1050.To The Max

2、求一个子段，它的和最大，子段的长度不小于 $L$。

子段和可以转化为前缀和相减的形式，即设 $su{m}_i$ 表示 $A_1$ ~ $A_i$ 的和，则有：
max ⁡ i − j ≥ L { A j + 1 + A j + 2 + . . . + A i } = max ⁡ L ≤ i ≤ n { s u m i − min ⁡ 0 ≤ j ≤ i − L { s u m j } } \max_{\mathclap{i - j \ge L}} \{ A_{j + 1} + A_{j + 2} + ... + A_i\} = \max_{L \le i \le n}\{ sum_i - \min_{0 \le j \le i - L}\{sum_j\}\} i−j≥Lmax​{Aj+1​+Aj+2​+...+Ai​}=L≤i≤nmax​{sumi​−0≤j≤i−Lmin​{sumj​}}

仔细观察上式可以发现，随着 $i$ 的增长，$j$ 的取值范围 0 ~ $i$ - $L$ 每次只会增大 1。换言之，每次只会有一个新的取值进入 min ⁡ { s u m j } \min\{sum_j\} min{sumj​} 的候选集合，所以没有必要每次循环枚举 $j$，只需要用一个变量记录当前最小值，每次与新的取值 $su{m}_{i-L}$ 取 $\min$ 就可以了。

double ans = -1e10;
double min_val = 1e10;
for (int i = L; i <= N; i++) {
	min_val = min(min_val, sum[i - L]);
	ans = max(ans, sum[i] - min_val);
}
1
2
3
4
5
6

解决了问题2之后，只需要看一下最大子段和是不是非负数，就可以确定二分上下界的变化范围了。

本题来源于POJ-2018.Best Cow Fences

代码

#include 
using namespace std;

const int N = 100005;
double a[N], b[N], sum[N];

int n, L;

bool check(double mid) {
    for (int i = 1; i <= n; i++) 
        b[i] = a[i] - mid; //每个数减去二分的值
    
    for (int i = 1; i <= n; i++) 
        sum[i] = sum[i - 1] + b[i]; //前缀和
    
    double ans = -1e10; 
    double min_val = 1e10;
    //子段长度不小于L的最大子段和
    for (int i = L; i <= n; i++) {
        min_val = min(min_val, sum[i - L]);
        ans = max(ans, sum[i] - min_val);
    }
 	//是否存在一个长度不小于L的子段，子段和非负
    return ans >= 0;
}

int main() {
    cin >> n >> L;
    
    for (int i = 1; i <= n; i++) 
        scanf("%lf", &a[i]);
    
    double eps = 1e-5;
    double l = -1e6;
    double r = 1e6;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << int (r * 1000) << endl; 
    return 0;
}
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
40
41
42
43