专栏文章

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

llogicneko
P14361题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minfjegu
此快照首次捕获于
2025/12/02 01:35
3 个月前
此快照最后确认于
2025/12/02 01:35
3 个月前
查看原文
反悔贪心
赛时 15min15min 写完了正解。
注意到明显的结论，如果有一组人数大于 n2\frac{n}{2} 那么把多出 n2\frac{n}{2} 的部分，给到其他任意一组，其人数总不多于 n2\frac{n}{2}。
有明显的贪心想法，让每一个人线选择自己最满意的部门，然后如果存在人数大于 n2\frac{n}{2} 的部门就把他挪到使其满意度减小最小的部门，用什么有序的东西维护一下，让每一次都使总满意度减少最小即可。
通过了民间数据。
CPP
#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 和一堆异或做这个事情，应该实现起来会比一推判断好写吧。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...