最佳牛围栏

https://www.acwing.com/problem/content/104/

思路：二分答案，根据二分的特性，二分的平均值答案总符合，其一边的答案是满足条件的，另一边的答案是不满足条件的。由于二分的平均值是实数，故采用实数二分

check函数思路：判断本二分答案 ave 的正确性，即判断是否存在一个长度大于等于 f 的区间，使得该区间的平均值大于等于 ave。为了便于检验，我们将原数组 a[] 每一个值都减去ave，这样问题就转化成了是否存在某一段长度大于等于f的子区间的和大于等于 0，具体区间和计算可以采取前缀和来维护，遍历过程中用一个变量记录前面的最小前缀和，具体过程见代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

int n, f;
double a[N], s[N];

bool check(double ave){
    for(int i = 1; i <= n; i ++){ // 计算前缀和
        s[i] = s[i - 1] + a[i] - ave;
    }
    double mi = 0;
    for(int i = 0, j = f; j <= n; i ++, j ++){
        mi = min(mi, s[i]); // 前 i 段中的最小前缀和
        if(s[j] - mi >= 0) return true;
    }
    return false;
}

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

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> f;
    double l = 0, r = 0;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        r = max(r, a[i]);
    }
    int res = erfen(l, r);
    cout << res << '\n';
    return 0;
}