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

zhao_ry514114 · 2025-11-01 21:31:11 · 题解

某初三蒟蒻本来还想半小时切T1来着

赛时看到T1被吓到了。。

读假题了开始想三维DP（其实也写不出来

想死的心都有了

后来发现是题目信息读漏了

于是开始重构代码——

算是贪心

题目中比较关键的一点是 n 为偶数且不存在一个部门被分配多于 \frac{n}{2} 个新成员

不难得出如果某一个部门人数超过了 \frac{n}{2} ，把多余的人无论如何分配到另外两个部门，都不会使另外两个部门人数超过 \frac{n}{2}

那么如何调整人数

肯定是选择损失最少的方案，比如部门1人太多，需要把一些人从部门1调到部门2或3。对于每个原本选择部门1的成员，如果调到部门2，满意度损失是 x - y；如果调到部门3，损失是 x - z

取这两个损失中的较小值，作为这个成员的调整代价

按调整代价从小到大排序，优先调整那些代价最小的人

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
struct xx { int x, y, z; }a[N];
// 按代价排序
bool cmp1 (xx A, xx B) {
    return min (A.x - A.y, A.x - A.z) < min (B.x - B.y, B.x - B.z);
}
bool cmp2 (xx A, xx B) {
    return min (A.y - A.x, A.y - A.z) < min (B.y - B.x, B.y - B.z);
}
bool cmp3 (xx A, xx B) {
    return min (A.z - A.y, A.z - A.x) < min (B.z - B.y, B.z - B.x);
}
int main () {
    ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while (t --) {
        int n;
        cin >> n;
        int c1 = 0, c2 = 0, c3 = 0， s = 0;
        for (int i = 0; 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) c1 ++;
            else if (a[i].y > a[i].x && a[i].y > a[i].z) c2 ++;
            else c3 ++;
            s += max (a[i].x, max (a[i].y, a[i].z));
        }
        // 人数调整
        if (c1 > n / 2) {
            sort (a, a + n, cmp1);
            for (int i = c2 + c3 ; i < n; i ++) {
                if (c1 == n / 2) break;
                s -= min (a[i].x - a[i].y, a[i].x - a[i].z);
                c1 --;
            }
        }
        else if (c2 > n / 2) {
            sort (a, a + n, cmp2);
            for (int i = c1 + c3; i < n; i ++) {
                if (c2 == n / 2) break;
                s -= min (a[i].y - a[i].x, a[i].y - a[i].z);
                c2 --;
            }
        }
        else if (c3 > n / 2){
            sort (a, a + n, cmp3);
            for (int i = c1 + c2; i < n; i ++) {
                if (c3 == n / 2) break;
                s -= min (a[i].z - a[i].x, a[i].z - a[i].y);
                c3 --;
            }
        }
        cout << s << '\n';
    }
    return 0;
}