【题解】POJ P2018【Best Cow Fences】

分析

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

代码

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 100000 + 6; 
double a[MAXN],b[MAXN],sum[MAXN];

inline double min(double a,double b){return a < b ? a : b;}
inline double max(double a,double b){return a > b ? a : b;}

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

    return 0;
}