[CSP-S 2025] 社团招新 / club

_H17_ · 2025-11-01 19:50:12 · 题解

前言

我是不是赢在这个题 1 分钟秒了？这是不是矛盾的病句。

题目分析

首先默认全选满意度最大的社团，如果合法肯定就是答案，这一定最优。

考虑不合法，对人最多的社团移走一些人即可。由于要移到 \frac{n}{2} 人为止一定最优，不需要考虑因此其他集合元素超出限制的情况。可以预处理每个人到她次喜欢的社团的满意度差。直接排序贪心选最小的即可。

时间复杂度 O(n\log n)，好像可以用桶做到 O(n)。

代码

#include<bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
using namespace std;
constexpr int N=1e5+1;
int T,n,a[N][4],maxv,ans;
vector<int>members[4];
void Main(){
    for(int i=1;i<=3;i++)
        members[i].clear();
    ans=0;
    cin>>n;
    for(int i=1,x,y;i<=n;i++){
        cin>>a[i][1]>>a[i][2]>>a[i][3];
        if(a[i][1]>=a[i][2]&&a[i][1]>=a[i][3]){
            x=1,
            y=(a[i][2]>a[i][3]?2:3);
        }
        else if(a[i][2]>=a[i][1]&&a[i][2]>=a[i][3]){
            x=2,
            y=(a[i][1]>a[i][3]?1:3);
        }
        else{
            x=3,
            y=(a[i][1]>a[i][2]?1:2);
        }
        members[x].push_back(a[i][x]-a[i][y]);
        ans+=a[i][x];
    }
    if((maxv=max({members[1].size(),members[2].size(),members[3].size()}))<=n/2)
        cout<<ans<<'\n';
    else{
        int x=(members[1].size()==maxv?1:(members[2].size()==maxv?2:3)),rem=members[x].size()-(n/2);
        sort(ALL(members[x]));
        for(int i=0;i<rem;i++)
            ans-=members[x][i];
        cout<<ans<<'\n';
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr),cout.tie(nullptr);
    for(cin>>T;T;--T)
        Main();
    return 0;
}