题解：P12545 [UOI 2025] Partitioning into Three

2huk · 2026-01-27 07:54:39 · 题解

首先破环为链。

不妨令分成的三段为 A,B,C。不妨令 A 是最大的，即 A \ge B,A \ge C。注意到因为在环上所以任意一种划分都能对应一种顺序使得第一段最大。

如果确定了 A（即确定了 x,y），那么 B,C 一定越接近越好。形式化的。z 是满足使得 B \ge C 最小的，或者是使得 B \le C 最大的。

那么当 x 固定时，z 是随着 y 增大而不减的。

考虑 y。在 A 保持最大的情况下，为了使答案最优，y 一定越小越好。

即 y 是使得 A \ge B,A \ge C 的最小数。那么 y 是随着 x 增大而不减的。

于是考虑一个「三指针」。复杂度线性。

为了好写 z 可以二分找，复杂度 \mathcal O(n \log n)。具体的它是不超过总和一半的最大值或不小于总和一半的最小值。

:::success[Code]

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e6 + 10;

int n, a[N], s[N];

pair<int, int> work(int l, int r) {
    int k = s[r] - s[l - 1];
    int p = lower_bound(s + l, s + r + 1, s[l - 1] + k / 2) - s;
    pair<int, int> res = {1e18, 1e18};
    if (p - 1 > l && p - 1 <= r) res = {max(s[p - 1 - 1] - s[l - 1], s[r] - s[p - 1 - 1]), p - 1};
    if (p > l && p <= r) res = min(res, make_pair(max(s[p - 1] - s[l - 1], s[r] - s[p - 1]), p));
    if (p + 1 > l && p + 1 <= r) res = min(res, make_pair(max(s[p - 1 + 1] - s[l - 1], s[r] - s[p + 1 - 1]), p + 1));
    return res;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++ i ) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    for (int i = 1; i <= 2 * n; ++ i ) s[i] = s[i - 1] + a[i];

    int ans = 1e18;
    int x, y, z;
    for (int i = 1, j = 1; i <= n; ++ i ) {
        j = max(j, i + 1);
        while (j < i + n - 1 && s[j - 1] - s[i - 1] < work(j, i + n - 1).first) {
            j ++ ;
        }
        if (j < i + n - 1) {
            int p = work(j, i + n - 1).second;
            int t0 = s[j - 1] - s[i - 1];
            int t1 = s[p - 1] - s[j - 1];
            int t2 = s[n] - t0 - t1;
            assert(t0 >= t1);
            assert(t0 >= t2);
            if (t0 - min(t1, t2) < ans) {
                ans = t0 - min(t1, t2);
                x = i, y = j, z = p;
            }
        }
    }
    if (x > n) x -= n;
    if (y > n) y -= n;
    if (z > n) z -= n;

    if (x > y) swap(x, y);
    if (y > z) swap(y, z);
    if (x > y) swap(x, y);
    cout << ans << '\n' << x << ' ' << y << ' ' << z << '\n';

    return 0;
}

:::