贪心 [CSP-S 2025] 社团招新

[CSP-S 2025] 社团招新

CSP/NOIP 正在 ACM 化. 前几年 T1 送分往往都是写个模拟即可, 但现在变成考思维题了.

显然我们不妨先不管 \(\dfrac{n}{2}\) 的限制, 一股脑直接去把人扔到对应的社团里, 在从人数最多的社团里把多余的人给换到其它社团.
因为我们的限制是 \(\dfrac{n}{2}\), 所以当一个社团人达到 \(\dfarc{n}{2}\) 时, 另外两个社团人数分别均不超过 \(\dfrac{n}{2}\), 显然可行. 下一个问题就是将哪些人给换走.
显然换走人会产生使满意度下降, 我们的目的是要让满意度下降最少, 即最大值减去次大值要尽可能的小. 优先把这种人换到其它社团.

代码:

#include<iostream>
#include<algorithm>
#include<vector>
#define P(A) A=-~A
#define NUMBER1 100000
typedef long long LL;
struct Satify{int a[3],rank_place[3],max,mid,min;inline void inint(){int res=0;res=max=min=a[0],rank_place[0]=rank_place[2]=rank_place[1]=0;for(int j=1;j<3;P(j)){if(a[j]>max)max=a[j],rank_place[0]=j;else if(a[j]<min)min=a[j],rank_place[2]=j;res+=a[j];}rank_place[1]=3-rank_place[0]-rank_place[2],mid=res-max-min;}bool operator<(const Satify &A)const{return max-mid<A.max-A.mid;}
}student[NUMBER1+5];
int cnt[3],ans;
inline void solve(){ans=cnt[0]=cnt[1]=cnt[2]=0;int n,half_n,need_remove(0);std::cin>>n;half_n=n>>1;for(int i=1;i<=n;P(i)){for(int j=0;j<3;P(j))std::cin>>student[i].a[j];student[i].inint();}for(int i=1;i<=n;P(i))P(cnt[student[i].rank_place[0]]),ans+=student[i].a[student[i].rank_place[0]];for(int j=0;j<3;P(j))if(cnt[j]>half_n){need_remove=j;break;}std::sort(student+1,student+1+n);for(int i=1;i<=n&&cnt[need_remove]>half_n;P(i)){if(student[i].rank_place[0]^need_remove)continue;--cnt[need_remove],ans=ans-student[i].a[need_remove]+student[i].a[student[i].rank_place[1]],P(cnt[student[i].rank_place[1]]);}std::cout<<ans<<'\n';
}
signed main(){std::cin.tie(nullptr)->std::ios::sync_with_stdio(false);std::cout.tie(nullptr);int T;std::cin>>T;while(T--)solve();return 0;
}