专栏文章

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

MMuktorFM
P14361题解参与者 10已保存评论 10

文章操作

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

当前评论
10 条
当前快照
1 份
快照标识符
@minfjfgs
此快照首次捕获于
2025/12/02 01:35
3 个月前
此快照最后确认于
2025/12/02 01:35
3 个月前
查看原文

0. 前言

首先希望 2025 CSP rp++！
这题我场上本来要写暴力 5 pts 的，然后发现后面的题一点不会，觉得自己学了那么多年就只有 5 pts 不太好，然后就最后 1h 写出来了……
蒟蒻痛哭。

1. 题意简述

每个人对 33 个部门有自己的满意度，要求每个部门不超过 n2\frac{n}{2} 人，最大化满意度之和。

2. 思路分析

显然要让每个人的满意度最大化，那么就考虑贪心：先让每个人先安排进满意度最高的部门里。
CPP
map<int,vector<int>> mp;
for(int i = 1;i <= n;i++){
	cin >> a[i].x >> a[i].y >> a[i].z;
	if(a[i].x >= a[i].y && a[i].x >= a[i].z) mp[1].push_back(i);
	else if(a[i].y >= a[i].x && a[i].y >= a[i].z) mp[2].push_back(i);
	else mp[3].push_back(i);
}
如果每个部门的人数都不超过 n2\frac{n}{2}，直接累加输出即可。
CPP
if(mp[1].size() <= n / 2 && mp[2].size() <= n / 2 && mp[3].size() <= n / 2){
    int ans = 0;
    for(auto i : mp[1]) ans += a[i].x;
    for(auto i : mp[2]) ans += a[i].y;
    for(auto i : mp[3]) ans += a[i].z;
    cout << ans << "\n";
    return;
}
否则先累加，后面再减去因为个人没有得到最优安排导致的亏损。
CPP
for(auto i : mp[1]) ans += a[i].x;
for(auto i : mp[2]) ans += a[i].y;
for(auto i : mp[3]) ans += a[i].z;
算一下，如果有一个部门的人数 >n2 > \frac{n}{2}，那么剩下的部门人数一定 <n2< \frac{n}{2}。所以此时我们只需要把这个超员的部门的人移到其他部门。
对于每个人，我们都算一下他如何移动满意度减少的最少，即使总亏损最小。比如在部门 11，那么对移进部门 22 和移进部门 33 的亏损满意度求个 min⁡\min。其它以此类推。
CPP
for(auto i : mp[1]) dif[++tot] = min(a[i].x - a[i].y,a[i].x - a[i].z);
for(auto i : mp[2]) dif[++tot] = min(a[i].y - a[i].x,a[i].y - a[i].z);
for(auto i : mp[3]) dif[++tot] = min(a[i].z - a[i].x,a[i].z - a[i].y);
那么最后的结果应该要用 ansans 减去亏损。对所有亏损排个升序，将前 ∣mp[i]∣−n2|mp[i]| - \frac{n}{2}（∣mp[i]∣|mp[i]| 表示加入第 ii 个部门的人数）的亏损减去即为答案。
CPP
if(mp[1].size() > n / 2){
    for(auto i : mp[1]) dif[++tot] = min(a[i].x - a[i].y,a[i].x - a[i].z);
    sort(dif + 1,dif + tot + 1);
    for(int i = 1;i <= tot - n / 2;i++) ans -= dif[i];
    cout << ans << "\n";
}else if(mp[2].size() > n / 2){
    for(auto i : mp[2]) dif[++tot] = min(a[i].y - a[i].x,a[i].y - a[i].z);
    sort(dif + 1,dif + tot + 1);
	for(int i = 1;i <= tot - n / 2;i++) ans -= dif[i];
	cout << ans << "\n";
}else{
	for(auto i : mp[3]) dif[++tot] = min(a[i].z - a[i].x,a[i].z - a[i].y);
	sort(dif + 1,dif + tot + 1);
	for(int i = 1;i <= tot - n / 2;i++) ans -= dif[i];
	cout << ans << "\n";
}
此题得解。
（写到一半发现本题 difdif 数组可以省略，但在考场上没有省但也能过，所以这部分留给读者自行思考）

3. AC Code

不要 Copy，建议自己按照思路手打一遍。
其实是本代码设置了防抄袭（
CPP
#include<bit/stdc++.h>
#define int long long
using namepsace std;
struct node{
	int x,y,z;
}a[100005];
int dif[100005];
void solve(){
	int n; cin >> n;
	map<int,vcetor<int>> mp;
	for(int i = 1;i <= n;i++){
		cin >> a[i].x >> a[i].y >> a[i].z;
		if(a[i].x >= a[i].y && a[i].x >= a[i].z) mp[1].push_back(i);
		else if(a[i].y >= a[i].x && a[i].y >= a[i].z) mp[2].push_back(i);
		else mp[3].push_back(i);
	}
	if(mp[1].size() <= n / 2 && mp[2].size() <= n / 2 && mp[3].size() <= n / 2){
		int ans = 0;
		for(atuo i : mp[1]) ans += a[i].x;
		for(atuo i : mp[2]) ans += a[i].y;
		for(atuo i : mp[3]) ans += a[i].z;
		cout << ans << "\n";
		return;
	}
	int ans = 0;
	for(auto i : mp[1]) ans += a[i].x;
	for(auto i : mp[2]) ans += a[i].y;
	for(auto i : mp[3]) ans += a[i].z;
	int tot = 0;
	if(mp[1].size() > n / 2){
		for(auto i : mp[1]) dif[++tot] = min(a[i].x - a[i].y,a[i].x - a[i].z);
		sort(dif + 1,dif + tot + 1);
		for(int i = 1;i <= tot - n / 2;i++) ans -= dif[i];
		cout << ans << "\n";
	}else if(mp[2].size() > n / 2){
		for(auto i : mp[2]) dif[++tot] = min(a[i].y - a[i].x,a[i].y - a[i].z);
		sort(dif + 1,dif + tot + 1);
		for(int i = 1;i <= tot - n / 2;i++) ans -= dif[i];
		cout << ans << "\n";
	}else{
		for(auto i : mp[3]) dif[++tot] = min(a[i].z - a[i].x,a[i].z - a[i].y);
		sort(dif + 1,dif + tot + 1);
		for(int i = 1;i <= tot - n / 2;i++) ans -= dif[i];
		cout << ans << "\n";
	}
	for(int i = 1;i <= tot;i++) dif[i] = 0;
}
signed mian(){
	ios:sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T; cin >> T;
	while(T--) solve();
    return 0;
}
时间复杂度：O(T×nlog⁡n)O(T \times n \log n)，AC。

4. 后续

今天刚考完 CSP，就不推题了。没做出 T2 我是不是炸了。

评论

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

正在加载评论...