题解 P8424 【[JOI Open 2022] 跷跷板（Seesaw）】

Leasier · 2022-07-15 11:42:37 · 题解

容易发现每次拿掉最左或最右侧的砝码相当于将原来有砝码的区间 [l, r] 的 l 加一或 r 减一。

直接考虑最值是不方便的，注意到最初一定有一个 base = \frac{sum_n}{n} 的情况，不妨以此为基准，则我们希望的是 base 减去最小值和最大值减去 base 的和最小。

直接考虑区间左右端点的两种移动方式也是不方便的，于是我们假装去掉这个限制，则我们希望得到每移动一次后 base 减去最小值和最大值减去 base 分别最小的区间 [l_1, r_1], [l_2, r_2]。

不难想到 l_2 = l_1 + 1, r_2 = r_1 + 1。于是我们可以二分 / 双指针求出这 2(n - 1) 个区间。

贪心地，我们希望每步都取到该步对应的两个区间之一。事实上，注意到双指针维护区间时一定是在上一步的两个区间的基础上将左端点加一或右端点减一，于是感性理解一下，我们每步一定可以取到其对应的两个区间之一。

于是我们预处理出每两个区间对应的 base 减去最小值和最大值减去 base，把它们丢进 n - 1 个 pair 中，按照其中一维升序，相同时再按另一维升序，最后维护没有优先升序的那一维的后缀最大值即可。时间复杂度为 O(n \log n)。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;

typedef struct Pair_tag {
    double a;
    double b;
    Pair_tag(){}
    Pair_tag(double a_, double b_){
        a = a_;
        b = b_;
    }
} Pair;

ll sum[200007];
Pair pr[200007];

bool operator <(const Pair a, const Pair b){
    if (a.a != b.a) return a.a < b.a;
    return a.b < b.b;
}

int main(){
    int n;
    double base, suf = 0.0, ans = 1e9;
    cin >> n;
    for (register int i = 1; i <= n; i++){
        int a;
        cin >> a;
        sum[i] = sum[i - 1] + a;
    }
    base = 1.0 * sum[n] / n;
    for (register int i = 1, j = 1, x = n; i < n; i++){
        int len = n - i;
        j++;
        if (1.0 * (sum[x] - sum[j - 1]) / len > base){
            j--;
            x--;
        }
        pr[i] = Pair(base - 1.0 * (sum[x] - sum[j - 1]) / len, 1.0 * (sum[x + 1] - sum[j]) / len - base);
    }
    sort(pr + 1, pr + n);
    for (register int i = n - 1; i >= 1; i--){
        ans = min(ans, pr[i].a + suf);
        suf = max(suf, pr[i].b);
    }
    printf("%.10lf", ans);
    return 0;
}