Solution Of P11702 [ROIR 2025] 不平衡划分

Dr1fty · 2025-02-10 18:33:32 · 题解

Solution

感觉挺牛的题。

先放结论，事实上一共只有三种情况：

• 最大段长度为 n - k + 1，剩下段长度都为 1。
• 最大段为一个前缀 [1, i]，最小段为 [i + 1, i + 1]。
• 最大段为一个后缀 [i, n]，最小段为 [i - 1, i - 1]。

然后答案就是这三种情况的 \max。

我们简单解释一下，这样考虑：假设一开始所有数分成若干一段，然后经过若干次变换之后只剩 k 段的过程。

• 如果当前最大段是前缀且后面紧跟着最小段，那么如果最小段长度大于 2，那么把最小段最前面的一个数给最大段。
• 如果当前最大段是后缀且前面紧跟着最小段，同理。
• 否则当前最大段不是前缀也不是后缀，那么一定可以将前面一段的最后一个数或后面一段的最前一个数加进来。
• 如果最大段长度超出 n - k + 1，结束。

然后答案应该就是这整个过程中只有 k 段所有状态的最大值。

然而你会发现这几个状态一定会被上面的三种情况所覆盖。

因此就可以直接这么做。

Code

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

constexpr int N = 3e5 + 7;
int n, k, a[N], pre[N], suf[N];
i64 sum[N], res;

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    cin >> n >> k;

    fill (pre, pre + n + 2, (int)2e9);
    fill (suf, suf + n + 2, (int)2e9);

    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }

    for (int i = 1; i <= n; i ++) {
        pre[i] = min (pre[i - 1], a[i]);
    }

    for (int i = n; i >= 1; i --) {
        suf[i] = min (suf[i + 1], a[i]);
    }

    int l = n - k + 1;

    // case 1
    for (int i = l; i <= n; i ++) {
        i64 ans = sum[i] - sum[i - l];
        res = max(ans - min(pre[i - l], suf[i + 1]), res);
    }

    // case 2
    for (int i = 1; i < n; i ++) {
        int x = 2 + (i < n - 1);
        int y = (n - i + 1);
        if (k >= x && k <= y) {
            res = max(res, sum[i] - a[i + 1]);
        }
    }

    // case 3
    for (int i = n - 1; i; i --) {
        int x = 2 + (i > 1);
        int y = i + 1;
        if (k >= x && k <= y) {
            res = max(res, sum[n] - sum[i] - a[i]);
        }
    }

    cout << res << endl;
    return 0;
}