AcWing 102. 最佳牛围栏

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

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

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

1. 求一个子段，它的和最大，没有 “长度不小于 $L$” 这个限制。
   无长度限制的最大子段和问题是一个经典问题，只需 $\mathcal{O}(n)$ 扫描该数列，不断把新的数加入子段，当子段和变成负数时，把当前的整个子段清空。
   扫描过程中出现过的最大子段和即为所求。

2. 求一个子段，它的和最大，子段的长度不小于 $L$。
   子段和可以转化为前缀和相减的形式，即设 $sum_i$ 表示 $A_1 \sim A_i$ 的和，则有：
   $\max_{i - j \geq L} { A_{j + 1} + A_{j + 2} + \cdots + A_i } = \max_{L \leq i \leq n} { sum_i - \min_{0 \leq j \leq i - L} { sum_j } }$
   随着 $i$ 的增长，$j$ 的取值范围 $0 \sim i - L$ 每次只会增大 $1$。
   换言之，每次只会有一个新的取值进入 $\min { sum_j }$ 的候选集合，所以我们没有必要循环枚举 $j$，只需要用一个变量记录当前最小值，每次与新的取值 $sum_{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);
}

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

double a[100001], b[100001], sum[100001];
int main() {
    int N, L; cin >> N >> L;
    for (int i = 1; i <= N; i++) scanf("%lf", &a[i]);
    double eps = 1e-5;
    double l = -1e6, r = 1e6;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        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;
        for (int i = L; i <= N; i++) {
            min_val = min(min_val, sum[i - L]);
            ans = max(ans, sum[i] - min_val);
        }
        if (ans >= 0) l = mid; else r = mid;
    }
    cout << int(r * 1000) << endl;
}