最佳牛围栏

AcWing-102-最佳牛围栏

分析

见《进阶指南》第29页。

实现

#include <iostream>
#define inf 0x3f3f3f3f
using namespace std;

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

bool check (double val) {
    for (int i = 1; i <= n; ++ i) b[i] = a[i] - val;
    for (int i = 1; i <= n; ++ i) sum[i] = sum[i - 1] + b[i];
    
    double res = -inf, min_val = inf;
    for (int i = f; i <= n; ++ i) { // 求长度 ≥ f 的最大连续子段和
        min_val = min(min_val, sum[i - f]);
        res = max(res, sum[i] - min_val);
    }
    return res > 0;
}

int main () {
    scanf("%d%d", &n, &f);
    for (int i = 1; i <= n; ++ i) scanf("%lf", &a[i]);
    
    double l = -inf, r = inf, eps = 1e-6;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid) == true)
            l = mid;
        else
            r = mid;
    }
    printf("%d\n", int(1000 * r));
    return 0;
}