寻找段落

洛谷-P1419-寻找段落

分析

最大化平均值。

实现

#include <iostream>
#include <queue>
using namespace std;

const int N = 100010;
const double eps = 1e-5;
int n, S, T;
double a[N], sum[N];

bool check (double x) {
    for (int i = 1; i <= n; ++ i)
        sum[i] = sum[i - 1] + (a[i] - x);
    deque<int> dq;
    for (int i = S; i <= n; ++ i) {
        if (!dq.empty() && i - dq.front() > T)
            dq.pop_front();
        while (!dq.empty() && sum[i - S] < sum[dq.back()])
            dq.pop_back();
        dq.push_back(i - S);
        // sum[r] - sum[l - 1]
        if (!dq.empty() && sum[i] - sum[dq.front()] >= 0)
            return true;
    }
    return false;
}

int main () {
    scanf("%d%d%d", &n, &S, &T);
    for (int i = 1; i <= n; ++ i) scanf("%lf", &a[i]);

    double l = -10000, r = 10000;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid) == true)
            l = mid;
        else
            r = mid;
    }
    printf("%.3lf", l);
    return 0;
}