题解 P1419 【寻找段落】

kkksc03 · 2013-08-12 22:36:25 · 题解

By tinylic

首先看出答案满足单调性，可以二分答案，转化为判定性问题。

令最优平均值为k,对于所有合法序列[l..r],

尝试将分式变为整式：s[l..r]＞k*(r-l+1)无解。

移项，令b[i]=a[i]-k，s’[i]为b[1]..b[n]的和，则有

寻找长度在[s,t]内的子段和的最大值可以用单调队列解决，参考POJ2823。

这样就能通过O(n)的时间判定k是否可行，总复杂度O(nlogn)。

具体实现的细节参考标程。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define maxn 100010

using namespace std;

int n, s, t, i;
double l, r, mid, ans;
double a[maxn];
int b[maxn];
double sum[maxn];
int q[maxn];

bool check(double x) {
    int i, l = 1, r = 0;
    for (i = 1; i <= n; i++)
        a[i] = (double)b[i] - x;
    sum[0] = 0;
    for (i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i];
    for (i = 1; i <= n; i++) {
        if (i >= s) {
            while (r >= l && sum[i - s] < sum[q[r]])    r--;
            q[++r] = i - s;
        }
        if (l <= r && q[l] < i - t) l++;
        if (l <= r && sum[i] - sum[q[l]] >= 0) return true;
    }
    return false;
}

int main() {

    scanf("%d", &n);
    scanf("%d%d", &s, &t);
    for (i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    ans = l = -10000; r = 10000;
    while (r - l > 1e-5) {
        mid = (l + r) / 2;
        if (check(mid))
            ans = l = mid;
        else r = mid;
    }

    printf("%.3lf\n", ans);
    return 0;
}