题解：P14361 [CSP-S 2025] 社团招新 / club（民间数据）

stripe_python · 2025-11-01 21:07:26 · 题解

考场思路，过了民间数据，写篇题解。

如果没有 \dfrac{n}{2} 这条限制，一个显然的贪心就是将第 i 人放到满意度最高的社团里。

考虑先这样算出一个解，然后调整。

关键观察：\dfrac{n}{2}+\dfrac{n}{2}\ge n。如果这个解已经合法，则不需要调整；否则找到超过 \dfrac{n}{2} 的社团。根据观察，只需将这个社团中的人数降到 \dfrac{n}{2} 就必然合法。

注意到 P2541 的贪心，按最大值减去次大值升序排序，即定义一个“损失函数”，取出前面的人直到合法即可。

复现的考场代码：

#define int long long
const int N = 1e5 + 5;

int n;
struct node {
    pair<int, int> v[4];
    void init() {
        for (int i = 1; i <= 3; i++) cin >> v[i].first, v[i].second = i;
        sort(v + 1, v + 4, greater<pair<int, int>>());
    }
    int loss() const {return v[1].first - v[2].first;}
    bool operator< (const node& a) const {
        return loss() < a.loss();
    }
} a[N]; 
vector<node> vec[4];

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) a[i].init();
    for (int i = 1; i <= 3; i++) vec[i].clear();
    int res = 0;
    for (int i = 1; i <= n; i++) vec[a[i].v[1].second].emplace_back(a[i]), res += a[i].v[1].first;
    for (int i = 1; i <= 3; i++) {
        if ((int) vec[i].size() < n / 2) continue;
        sort(vec[i].begin(), vec[i].end());
        for (int j = 0; j < (int) vec[i].size() - n / 2; j++) res -= vec[i][j].loss();
    } cout << res << '\n';
} 

闲话：本人在这题写了两次假做法，花费 1.5h 才过大样例。