[数据结构与算法]【题解】AcWing 102.Best Cow Fences

AcWing 102.最佳牛围栏

题目描述

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

输出样例

6500

题目分析

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

如果把子段中每个数都减去 $avg$，就变成了判定这个子段和是否非负。

我们可以先求出序列的前缀和，对于长度不小于 $L$ 的子段和，只需 s u m [ i ] ? m i n { s u m [ j ] ∣ 0 ≤ j ≤ i ? L } sum[i]-min\{sum[j]|0\le j\le i-L\} sum[i]?min{sum[j]∣0≤j≤i?L} 即可。在枚举 $i$ 的同时可以通过前缀最小值更新 $mins$ 的值。我们只需判断 $sum[i]\ge mins$ 是否成立，若存在某个 $i$ 使得上式成立，则 $avg$ 可取到，将其作为左端点继续二分；否则 $avg$ 过大，将其作为右端点继续二分。

代码：

#include <iostream>
using namespace std;

const int N = 100050;
int a[N], n, f;
double sum[N];

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

    double mins = 0;
    for (int i = f, j = 0; i <= n; i ++, j ++){
        mins = min(mins, sum[j]);
        if (sum[i] >= mins) return 1;
    }
    return 0;
}

int main(){
    cin >> n >> f;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    double l = 1, r = 2000;
    while (r - l > 1e-5){
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << int(r * 1000);
    return 0;
}