P7795 [COCI2014-2015#7] PROSJEK 题解

Pengzt · 2023-02-15 21:58:07 · 题解

P7795

简单二分。

显然 \mathcal{O}(n ^ 2) 的时间复杂度无法通过。

使子段平均值最大，考虑二分。

可以二分平均值 mid，然后判断是否有满足条件的和 \ge 0 且长度 \ge k 的子段。

记录一个前缀和数组 s，变为对于每个 i，看是否存在 j(j<i) 使得 i-j\ge k 且 s_i\ge s_j。这个东西显然可以变为查询 s 的某一个前缀中是否存在一个值使得 s_j<s_i，从前往后扫一遍做一个前缀 \min 即可。

时间复杂度：\mathcal{O}(\dfrac{n\log V}{\text{eps}})，其中 \text{eps} 为设置的精度，V 为值域。

代码：

#include<bits/stdc++.h>

using ll = long long;
using pii = std::pair<int, int>;

const int N = 3e5 + 5;
const double eps = 1e-6;
int n, k;
int a[N];
double b[N];

bool check(double mid) {
    for (int i = 1; i <= n; i++) {
        b[i] = b[i - 1] + a[i] - mid;
    }
    double res = -1, mnv = 1e9;
    for (int i = k; i <= n; i++) {
        mnv = std::min(mnv, b[i - k]);
        res = std::max(res, b[i] - mnv);
    }
    return res >= 0;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    double l = 1, r = 1e6;
    while (l + eps < r) {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    printf("%.6lf\n", l);
    return 0;
}