题解 | #Best Cow Fences#

对于本题，需要发现平均值具有单调性，可以使用二分。如果给定了平均值。需要检查是否满足存在一个至少长度为的子数组，平均值大于给出的。实现为代码中的函数。

首先如果子数组没有长度限制求子数组最大值，可以求出一个数组的前缀和，对于任意子数组,区间和为。那么我们可以枚举,同时维护左边的对应的最小值，这样就可以求出子数组的最大值。

如果有了长度限制，只不过是让的长度大于而已。

这样我们可以减原数组都减去，然后判断是否有长度大于等于的子数组和大于0，如果有，说明这个平均值满足，否则不满足。

void solve(){ 
    int n,f; cin >> n >> f;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    vector<double> b(n);
    vector<double> presum(n + 1);
    auto check = [&](double mid) -> bool{
        for(int i = 0; i < n; i++){
            b[i] = a[i] - mid;
        }
        for(int i = 1; i <= n; i++){
            presum[i] = presum[i - 1] + b[i - 1];
        }

        double res = -inf,mn = inf;
        for(int i = f - 1; i < n; i++){
            mn = min(mn,presum[i - f + 1]);
            res = max(res,presum[i + 1] - mn);
            
        }
        return res >= 0;

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