POJ 2018 二分

题意

传送门 POJ 2018

题解

最大化平均值问题考虑二分答案，问题转化为判定是否存在一个长度大于等于 F F F 的子区间，使其平均数不小于二分值。设区间为 [ l , r ] [l,r] [l,r]，当前二分值为 x x x，则判定不等式为
∑ i ∈ [ l , r ] C [ i ] r − l + 1 ≥ x \frac{\sum_{i\in [l,r]}C[i]}{r-l+1}\geq x r−l+1∑i∈[l,r]​C[i]​≥x 左右两边乘上分母，移项后得到
∑ i ∈ [ l , r ] ( C [ i ] − x ) ≥ 0 \sum_{i\in[l,r]}(C[i]-x)\geq 0 i∈[l,r]∑​(C[i]−x)≥0

问题转换为求长度不小于 F F F 的最大子区间和。设 [ 1 , i ] [1,i] [1,i] 的前缀和为 s u m [ i ] sum[i] sum[i]，枚举右界，则答案为 m a x r ∈ [ F , N ] { s u m [ r ] − m a x l ∈ [ 0 , r − F ] s u m [ l ] } max_{r\in [F,N]}\{sum[r]-max_{l\in [0,r-F]}sum[l]\} maxr∈[F,N]​{sum[r]−maxl∈[0,r−F]​sum[l]}

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 100005
#define maxc 2005
#define eps 1e-6
int N, F, C[maxn];
double sum[maxn];

bool judge(double x)
{
    for (int i = 1; i <= N; ++i)
        sum[i] = C[i] - x + sum[i - 1];
    double res = -maxc * maxn, mn = maxc * maxn;
    for (int r = F; r <= N; ++r)
    {
        mn = min(mn, sum[r - F]);
        res = max(res, sum[r] - mn);
    }
    return res >= 0;
}

int main()
{
    scanf("%d%d", &N, &F);
    for (int i = 1; i <= N; ++i)
        scanf("%d", C + i);
    double lb = 0, ub = maxc;
    while (ub - lb > eps)
    {
        double mid = (lb + ub) / 2;
        if (judge(mid))
            lb = mid;
        else
            ub = mid;
    }
    printf("%d\n", int(1000 * ub));
    return 0;
}