题解：P14361 [CSP-S 2025] 社团招新 / club

· · 题解

0. 前言

首先希望 2025 CSP rp++！

这题我场上本来要写暴力 5 pts 的，然后发现后面的题一点不会，觉得自己学了那么多年就只有 5 pts 不太好，然后就最后 1h 写出来了……

蒟蒻痛哭。

1. 题意简述

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

2. 思路分析

显然要让每个人的满意度最大化，那么就考虑贪心：先让每个人先安排进满意度最高的部门里。

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);
}

如果每个部门的人数都不超过 \frac{n}{2}，直接累加输出即可。

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;
}

否则先累加，后面再减去因为个人没有得到最优安排导致的亏损。

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;

算一下，如果有一个部门的人数 > \frac{n}{2}，那么剩下的部门人数一定 < \frac{n}{2}。所以此时我们只需要把这个超员的部门的人移到其他部门。

对于每个人，我们都算一下他如何移动满意度减少的最少，即使总亏损最小。比如在部门 1，那么对移进部门 2 和移进部门 3 的亏损满意度求个 \min。其它以此类推。

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);

那么最后的结果应该要用 ans 减去亏损。对所有亏损排个升序，将前 |mp[i]| - \frac{n}{2}（|mp[i]| 表示加入第 i 个部门的人数）的亏损减去即为答案。

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";
}

此题得解。

（写到一半发现本题 dif 数组可以省略，但在考场上没有省但也能过，所以这部分留给读者自行思考）

3. AC Code

不要 Copy，建议自己按照思路手打一遍。

其实是本代码设置了防抄袭（

#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 \times n \log n)，AC。

4. 后续

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