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

· · 题解

反悔贪心

赛时 15min 写完了正解。

注意到明显的结论，如果有一组人数大于 \frac{n}{2} 那么把多出 \frac{n}{2} 的部分，给到其他任意一组，其人数总不多于 \frac{n}{2}。

有明显的贪心想法，让每一个人线选择自己最满意的部门，然后如果存在人数大于 \frac{n}{2} 的部门就把他挪到使其满意度减小最小的部门，用什么有序的东西维护一下，让每一次都使总满意度减少最小即可。

通过了民间数据。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n,sum=0;
        cin>>n;
        vector<int>cnt(3,0);
        priority_queue<int,vector<int>,greater<int>> q[3];
        for(int i=1;i<=n;i++){
            vector<int>a(3);
            cin>>a[0]>>a[1]>>a[2];
            int idx=max_element(a.begin(),a.end())-a.begin();
            cnt[idx]++;
            sum+=a[idx];
            int mn=*min_element(a.begin(),a.end());
            q[idx].push(a[idx]-(a[0]^a[1]^a[2]^a[idx]^mn));
        }
        for(int i=0;i<3;i++){
            if(cnt[i]<=n/2)
                continue;
            while(q[i].size()>n/2){
                sum-=q[i].top();
                q[i].pop();
            }
        }
        cout<<sum<<'\n';
    }
    return 0;
}

顺便一提，为了使减少最小，显然应当用三个数的最大数减去中位数，这里为了方便用了 max_element 和 min_element 和一堆异或做这个事情，应该实现起来会比一推判断好写吧。