题解：CF2157D Billion Players Game

WilliamFranklin · 2025-11-24 19:33:11 · 题解

Solution

首先排序，然后考虑对于一个点，若我们给他的限制为 \ge a_i，则称之为白点，用 A_i 表示。若给他的限制为 \le a_i，则称之为黑点，用 B_i 表示。

设 A 的大小为 cnt_A，B 的大小为 cnt_B。考虑对于对于一个 p，其价值为 \sum{(p - A_i)} + \sum{(B_i - p)} = -\sum{A_i} + \sum{B_i} + p(cnt_A - cnt_B)。我们想让这个东西最大，那么一定是 B 为 a 的一个后缀，A 为 a 的一个前缀。那么我们枚举这个 cnt_A - cnt_B，在 cnt_A - cnt_B < 0 时，p = r；在 cnt_A - cnt_B \ge 0 时，p = l。并且贪心的考虑，cnt_A - cnt_B 一定时，B 选的越多越好，因为一定 B_i \ge A_j。

:::success[AC Code]

#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; 
} 

:::