专栏文章

题解：CF2157D Billion Players Game

WWilliamFranklin
CF2157D题解参与者 3已保存评论 5

文章操作

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

当前评论
5 条
当前快照
1 份
快照标识符
@min1dfd2
此快照首次捕获于
2025/12/01 18:58
3 个月前
此快照最后确认于
2025/12/01 18:58
3 个月前
查看原文

Solution

首先排序，然后考虑对于一个点，若我们给他的限制为 ≥ai\ge a_i，则称之为白点，用 AiA_i 表示。若给他的限制为 ≤ai\le a_i，则称之为黑点，用 BiB_i 表示。
设 AA 的大小为 cntAcnt_A，BB 的大小为 cntBcnt_B。考虑对于对于一个 pp，其价值为 ∑(p−Ai)+∑(Bi−p)=−∑Ai+∑Bi+p(cntA−cntB)\sum{(p - A_i)} + \sum{(B_i - p)} = -\sum{A_i} + \sum{B_i} + p(cnt_A - cnt_B)。我们想让这个东西最大，那么一定是 BB 为 aa 的一个后缀，AA 为 aa 的一个前缀。那么我们枚举这个 cntA−cntBcnt_A - cnt_B，在 cntA−cntB<0cnt_A - cnt_B < 0 时，p=rp = r；在 cntA−cntB≥0cnt_A - cnt_B \ge 0 时，p=lp = l。并且贪心的考虑，cntA−cntBcnt_A - cnt_B 一定时，BB 选的越多越好，因为一定 Bi≥AjB_i \ge A_j。
AC CodeCPP
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 2e5 + 5;
int n;
long long l, r, a[N];
long long pre[N], suf[N];
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int T = 1;
	cin >> T;
	while (T--) {
		cin >> n >> l >> r;
		For(i, 1, n) cin >> a[i];
		sort(a + 1, a + n + 1); 
		For(i, 1, n) pre[i] = pre[i - 1] + a[i];
		suf[n + 1] = 0;
		Dec(i, n, 1) suf[i] = suf[i + 1] + a[i];
		long long ans = 0;
		For(i, 0, n) {
			int x = (n - i) / 2;
			int y = x + i;
			ans = max(ans, suf[n - y + 1] - pre[x] - 1ll * i * r);
		}
		For(i, 0, n) {
			int x = (n + i) / 2;
			int y = x - i;
			ans = max(ans, suf[n - y + 1] - pre[x] + 1ll * i * l);
		}
		cout << ans << '\n';
	}
	return 0; 
}

评论

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

正在加载评论...