题解：P14361 [CSP-S 2025] 社团招新 / club（官方数据）
chenzefan
·
·
题解
题目传送门
思路
不难发现题目要求 $O(t \times n \log n)$ 的时间复杂度。首先考虑直接排序求解。然后发现假了。（本人没想出这个写法，但不否认该思路。）
然后经过对大样例的极限瞪眼。知道了！
我们只需要先把每个成员对 $3$ 个部门的满意度最大值累计一下，如果某部门人数超出了 $\frac{n}{2}$，则可以进行删减。我们明显更需要减去一个更小的值，这样保留下来才能更大。考虑小根堆。
码量是有些大的。但是还是有些暴力。总的来讲应该在 $1 \operatorname{h}$ 左右想到的。但想了 $2 \operatorname{h}$ ~~(真菜)~~。
代码有些丑陋，就不给了。[AC 记录。](https://www.luogu.com.cn/record/244753357)
再问一句：这种思路就是**反悔贪心**吗？如果是的话，看样子也不难。
::::info[还是给一下代码吧（内含一些无关变量，请勿喷！）丑陋]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t,n,cnt1,cnt2,cnt3,ans;
struct node{int x,y,z;}a[N];
struct Node{
int x,y,z,w;
friend bool operator < (Node x,Node y){return x.x>y.x;}
};
bool work1(int x){
if(x==1) return cnt1==n/2;
if(x==2) return cnt2==n/2;
if(x==3) return cnt3==n/2;
}
void work2(int x){
if(x==1) cnt1++;
if(x==2) cnt2++;
if(x==3) cnt3++;
}
bool vis[N];
vector <int> vec[5];
priority_queue <Node> q;
signed main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);ans=cnt1=cnt2=cnt3=0;
while(!q.empty()) q.pop();
for(int i=1;i<=3;i++) vec[i].clear();
int m=n/2;
for(int i=1;i<=n;i++){
vis[i]=0;
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
int maxx=max({a[i].x,a[i].y,a[i].z});ans+=maxx;
if(maxx==a[i].x) cnt1++,vec[1].push_back(i);
else if(maxx==a[i].y) cnt2++,vec[2].push_back(i);
else cnt3++,vec[3].push_back(i);
}
if(cnt1<=m&&cnt2<=m&&cnt3<=m){printf("%d\n",ans);continue;}
if(cnt1>m){
for(int i=0;i<vec[1].size();i++){
int id=vec[1][i];
int k1=a[id].x-a[id].y,k2=a[id].x-a[id].z;
if(k1<k2) q.push({k1,a[id].x,2,id});
else q.push({k2,a[id].x,3,id});
}
while(cnt1>m){
Node u=q.top();q.pop();
if(vis[u.w]) continue;
if(work1(u.z)) continue;
cnt1--;vis[u.w]=1;
work2(u.z);
ans-=u.x;
}
printf("%d\n",ans);
continue;
}
if(cnt2>m){
for(int i=0;i<vec[2].size();i++){
int id=vec[2][i];
int k1=a[id].y-a[id].x,k2=a[id].y-a[id].z;
if(k1<k2) q.push({k1,a[id].y,1,id});
else q.push({k2,a[id].y,3,id});
}
while(cnt2>m){
Node u=q.top();q.pop();
if(vis[u.w]) continue;
if(work1(u.z)) continue;
cnt2--;vis[u.w]=1;
work2(u.z);
ans-=u.x;
}
printf("%d\n",ans);
continue;
}
for(int i=0;i<vec[3].size();i++){
int id=vec[3][i];
int k1=a[id].z-a[id].x,k2=a[id].z-a[id].y;
if(k1<k2) q.push({k1,a[id].z,1,id});
else q.push({k2,a[id].z,2,id});
}
while(cnt3>m){
Node u=q.top();q.pop();
if(vis[u.w]) continue;
if(work1(u.z)) continue;
cnt3--;vis[u.w]=1;
work2(u.z);
ans-=u.x;
}
printf("%d\n",ans);
}
return 0;
}
```
::::