LOJ#10012. Best Cow Fences

二分 + 前缀和
首先我们可以二分平均数
对于长度不小于L的子段，
（1）等价于原数组中的每个数减去平均数，计算度不小于L的子段使得和大于0
（2）通过一个变量维护，\((0,i-L)\)中前缀和的最小值

#include 
using namespace std;
const int N = 1e5 + 10;
const double eps = 1e-5;
int n, m;
double a[N];
double b[N], sum[N];
bool check(double mid)
{
    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 minn = 1e10;
    for (int i = m; i <= n; i ++ ) {
        minn = min(minn, sum[i - m]);
        if (sum[i] - minn >= 0) return true;
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )  scanf("%lf", &a[i]);
    double l = 0.0, r = 2010.0;
    while (r - l > eps) {
        double mid = (l+r) / 2.0;
        if (check(mid)) l = mid;
        else    r = mid;
    } 
    cout << (int)(r * 1000) << endl;
    return 0;
}