小 Ad-hoc

EricWan · 2025-04-07 13:41:31 · 题解

对于 n 是偶数和奇数分开考虑。

n 是偶数

我们的理论最大答案是前 \frac n2 大的数的和减后 \frac n2 大的和。

下证一定可以取到。

想象将这前 \frac n2 个数染蓝，将这后 \frac n2 个数染红，你期望蓝色数都产生正贡献，红色数都产生负贡献。

任何一个中间时刻，序列中一定存在蓝色和红色的数，所以就必定有一对相邻的不同色的数，我们就操作这一对数，因为蓝色的总不小于红色的，所以当前操作合法。问题规模减小，继续做即可。

n 是奇数

肯定恰好有一个元素没有被取到，我们可以证明这个元素下标一定是奇数。（显然，反证，如果它的某一侧元素数量是奇数，那一侧一定删不完）

然后我们就可以枚举这个活下来的数的位置，左右都使用 n 是偶数的方法处理即可。

维护方法是对顶堆，不会的可以学。

代码不短

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, a[1000005], ans, l[1000005], r[1000005];
set<pair<int, pair<int, int> > > st;
priority_queue<int> q1;
priority_queue<int, vector<int>, greater<int> > q2;
int s1, s2, ans1[1000005], ans2[1000005];
signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (1 & ~n) {
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n / 2; i++) {
            ans -= a[i];
        }
        for (int i = n / 2 + 1; i <= n; i++) {
            ans += a[i];
        }
        cout << ans << endl;
        return 0;
    }
    q1.push(-2e9);
    q2.push(2e9);
    for (int i = 1; i <= n; i += 2) {
        ans1[i] = s2 - s1;
        if (a[i] <= q1.top()) {
            s1 += a[i];
            q1.push(a[i]);
        }
        else {
            s2 += a[i];
            q2.push(a[i]);
        }
        if (a[i + 1] <= q1.top()) {
            s1 += a[i + 1];
            q1.push(a[i + 1]);
        }
        else {
            s2 += a[i + 1];
            q2.push(a[i + 1]);
        }
        if (q1.size() > q2.size()) {
            s1 -= q1.top();
            s2 += q1.top();
            q2.push(q1.top());
            q1.pop();
        }
        if (q2.size() > q1.size()) {
            s2 -= q2.top();
            s1 += q2.top();
            q1.push(q2.top());
            q2.pop();
        }
    }
    while (!q1.empty()) q1.pop();
    while (!q2.empty()) q2.pop();
    q1.push(-2e9);
    q2.push(2e9);
    s1 = s2 = 0;
    for (int i = n; i >= 1; i -= 2) {
        ans2[i] = s2 - s1;
        if (a[i] <= q1.top()) {
            s1 += a[i];
            q1.push(a[i]);
        }
        else {
            s2 += a[i];
            q2.push(a[i]);
        }
        if (a[i - 1] <= q1.top()) {
            s1 += a[i - 1];
            q1.push(a[i - 1]);
        }
        else {
            s2 += a[i - 1];
            q2.push(a[i - 1]);
        }
        if (q1.size() > q2.size()) {
            s1 -= q1.top();
            s2 += q1.top();
            q2.push(q1.top());
            q1.pop();
        }
        if (q2.size() > q1.size()) {
            s2 -= q2.top();
            s1 += q2.top();
            q1.push(q2.top());
            q2.pop();
        }
    }
    for (int i = 1; i <= n; i += 2) {
        ans = max(ans, ans1[i] + ans2[i]);
    }
    cout << ans << endl;
    return 0;
}