专栏文章

小 Ad-hoc

EEricWan
AT_arc196_a题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mipowelx
此快照首次捕获于
2025/12/03 15:32
3 个月前
此快照最后确认于
2025/12/03 15:32
3 个月前
查看原文
对于 nn 是偶数和奇数分开考虑。

nn 是偶数

我们的理论最大答案是前 n2\frac n2 大的数的和减后 n2\frac n2 大的和。
下证一定可以取到。
想象将这前 n2\frac n2 个数染蓝，将这后 n2\frac n2 个数染红，你期望蓝色数都产生正贡献，红色数都产生负贡献。
任何一个中间时刻，序列中一定存在蓝色和红色的数，所以就必定有一对相邻的不同色的数，我们就操作这一对数，因为蓝色的总不小于红色的，所以当前操作合法。问题规模减小，继续做即可。

nn 是奇数

肯定恰好有一个元素没有被取到，我们可以证明这个元素下标一定是奇数。（显然，反证，如果它的某一侧元素数量是奇数，那一侧一定删不完）
然后我们就可以枚举这个活下来的数的位置，左右都使用 nn 是偶数的方法处理即可。
维护方法是对顶堆，不会的可以学。
代码不短
CPP
#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;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...