2025 社团招新 · 方案二超额排序移人

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1599 字

每人先取最大值，超额部门按搬离代价升序扣最小几人

2025
贪心

正文

// CSP-S 2025 复赛 T1 · 社团招新（方案二：排序批量移人，满分）
// 原题：https://oj.yecheng.tv/p/2466
// 题意：同方案一（n 保证为偶数，T ≤ 5、n ≤ 1e5，需满分口径）。
// 思路（把方案一的「逐次移人」一次算清）：
//   与方案一相同，每人先取最大值；超额部门 p 里每个人的「搬离代价」
//   cost = a[i][p] - max(另两部门)，把代价升序排序，
//   需要移走 cnt[p] - n/2 人，直接取前若干小的代价扣掉即可。
//   正确性与逐次移人一致：每次总是搬走当前代价最小的人，且搬走
//   一个人不会改变其他人进其余两部门的代价上界。
// 复杂度：每组 O(n log n)，全数据通过。
// 易错点：
//   1. 只对超额部门处理，移走人数恰好 = cnt[p] - n/2；
//   2. 代价排序后取前 k 小求和，k = cnt[p] - n/2；
//   3. 多组数据注意每组的 cnt 数组清零。
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        vector<array<ll, 3>> a(n);
        vector<int> asg(n, -1);
        ll ans = 0;
        int cnt[3] = {0, 0, 0};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) scanf("%lld", &a[i][j]);
            int p = 0;
            for (int j = 1; j < 3; j++)
                if (a[i][j] > a[i][p]) p = j;
            asg[i] = p;
            ans += a[i][p];
            cnt[p]++;
        }
        for (int p = 0; p < 3; p++) {
            if (cnt[p] <= n / 2) continue;
            vector<ll> cost;
            for (int i = 0; i < n; i++)
                if (asg[i] == p) {
                    int q1 = (p + 1) % 3, q2 = (p + 2) % 3;
                    cost.push_back(a[i][p] - max(a[i][q1], a[i][q2]));
                }
            sort(cost.begin(), cost.end());
            for (int k = 0; k < cnt[p] - n / 2; k++) ans -= cost[k];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

2025 社团招新 · 方案二 超额排序移人

正文

CSP-S 标程 · 复赛真题的其它内容

2025 社团招新 · 方案二超额排序移人