[CSP-S 2025] 社团招新

GitHub跳转原题关系图返回列表

先让每个人去最满意的部门，若唯一超员部门超过上限，就按最小转出损失修正。

OJ: luogu

题目 ID: P14361

难度:普及+/提高

标签:贪心排序构造

日期: 2026-06-22 19:41

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

有 n 个新成员，n 是偶数。每个成员分到三个部门之一，分到第 j 个部门会获得满意度 a[i][j]。

要求每个部门的人数都不超过 n/2，在这个限制下最大化总满意度。

思路

先看一个可以直接验证想法的朴素解：

cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n, limit_num;
int a[MAXN][4];
int cnt[4];
long long best_ans;

void dfs(int pos, long long sum) {
    if (pos > n) {
        best_ans = max(best_ans, sum);
        return;
    }

    for (int dep = 1; dep <= 3; dep++) {
        if (cnt[dep] == limit_num) {
            continue;
        }
        cnt[dep]++;
        dfs(pos + 1, sum + a[pos][dep]);
        cnt[dep]--;
    }
}

void solve_case() {
    cin >> n;
    limit_num = n / 2;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][1] >> a[i][2] >> a[i][3];
    }

    cnt[1] = cnt[2] = cnt[3] = 0;
    best_ans = -1;
    dfs(1, 0);
    cout << best_ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve_case();
    }

    return 0;
}

暴力会枚举每个人分到哪个部门，并检查三个部门人数是否都不超过 n/2。这个做法能直接表达题意，但复杂度是 O(3n)O(3^n)，不能用于正式数据。

先忽略人数限制。对每个人来说，显然应该把他分到自己最满意的部门。这样得到一个无约束最优方案。

如果这个方案已经满足每个部门不超过 n/2，答案就是它。

如果不满足，最多只会有一个部门超员。因为如果两个部门都超过 n/2，这两个部门人数之和就已经超过 n。

设超员部门为 x，当前人数为 cnt[x]，需要挪走：

text
cnt[x] - n/2

个人。对于一个原本分到 x 的人，把他转到另两个部门中更满意的那个，造成的最小损失是：

text
a[i][x] - max(a[i][y], a[i][z])

所以只需要把这些损失排序，减去最小的若干个。

还要注意一个容易担心的问题：另两个部门会不会装不下这些被挪走的人？

设 m = n/2，需要挪走 s = cnt[x] - m 人。另两个部门为 y,z，则：

text
m - cnt[y] = cnt[z] + s >= s
m - cnt[z] = cnt[y] + s >= s

也就是说，另两个部门中的任意一个，空位都至少有 s 个。因此每个被挪走的人都可以独立选择另两个部门中满意度更高的那个，不会被容量卡住。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
int cnt[4];                 // cnt[j] 表示当前分到第 j 个部门的人数
vector<int> loss[4];        // loss[j]：从第 j 个部门挪走某个人造成的满意度损失

void clear_case() {
    for (int i = 1; i <= 3; i++) {
        cnt[i] = 0;
        loss[i].clear();
    }
}

void solve_case() {
    cin >> n;
    clear_case();

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int a[4];
        cin >> a[1] >> a[2] >> a[3];

        int best = 1;
        if (a[2] > a[best]) {
            best = 2;
        }
        if (a[3] > a[best]) {
            best = 3;
        }

        int second_best = 0;
        for (int j = 1; j <= 3; j++) {
            if (j == best) {
                continue;
            }
            second_best = max(second_best, a[j]);
        }

        ans += a[best];
        cnt[best]++;
        loss[best].push_back(a[best] - second_best);
    }

    int limit = n / 2;
    int over = 0;
    for (int j = 1; j <= 3; j++) {
        if (cnt[j] > limit) {
            over = j;
        }
    }

    if (over != 0) {
        int need_move = cnt[over] - limit;
        sort(loss[over].begin(), loss[over].end());
        for (int i = 0; i < need_move; i++) {
            ans -= loss[over][i];
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve_case();
    }

    return 0;
}

复杂度

每个人只处理一次。若存在超员部门，只需要排序这个部门的损失数组。

单组数据时间复杂度为：

text
O(n log n)

空间复杂度为 O(n)O(n)。

总结

本题的核心是“先取无约束最优，再修正唯一可能超员的部门”。修正时，每个原本分到超员部门的人都有一个独立的转出损失，选最小的若干个即可。

平局不需要特殊处理：如果某个人对另一个部门同样满意，他的转出损失就是 0，排序时自然会优先被选中。