[CSP-S 2025] 社团招新

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

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

OJ: luogu

题目 ID: P14361

难度:普及

标签:贪心排序构造

创建: 2026-06-22 19:41

更新: 2026-10-07 10:45

题意

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

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

思路

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

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 22:53
 * update_at: 2026-10-01 22:53
 */
// brute.cpp：小数据暴力解，递归枚举每个人分到哪个部门，用来帮助理解题意并辅助对拍。
// 只适合 n ≤ 10 的对拍场景。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 15;

ll n, limit_num;
int a[MAXN][4]; // a[i][j] = 第 i 个人对第 j 个部门的满意度
int cnt[4];     // 各部门当前人数
ll best_ans;

// dfs(pos, sum)：已分配前 pos-1 个人，当前满意度为 sum，继续分配第 pos 个人。
void dfs(ll pos, ll 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 (ll 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);

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

    return 0;
}

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

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

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

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

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

text

1cnt[x] - n/2

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

text

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

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

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

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

text

1
2m - cnt[y] = cnt[z] + s >= s
m - cnt[z] = cnt[y] + s >= s

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

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 22:53
 * update_at: 2026-10-01 22:53
 */
// main.cpp：满分做法，贪心 + 补偿：每人先分到满意度最高的部门，
// 若某部门超员，把"损失最小"的人挪到次优部门。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

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

    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        int a[4]; // a[j] = 第 i 个人对第 j 个部门的满意度（≤ 2*10^4，int 足够）
        cin >> a[1] >> a[2] >> a[3];

        // 找满意度最高的部门（best）和次高的满意度（second_best）。
        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 = (int)(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);

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

    return 0;
}

复杂度

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

单组数据时间复杂度为：

text

1O(n log n)

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

总结

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

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

P14361 [CSP-S 2025] 社团招新

题目描述

小 L 是学校算法协会的成员。在今年的学校社团招新中，小 L 一共招收了 $n$ 个新成员，其中 $n$ 为偶数。现在小 L 希望将他们分到协会不同的部门。

算法协会共设有三个部门，其中第 $i$ ( $1 \leq i \leq n$ ) 个新成员对第 $j$ ( $1 \leq j \leq 3$ ) 个部门的满意度为 $a_{i,j}$ 。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和，也就是说，若将第 $i$ ( $1 \leq i \leq n$ ) 个新成员分配到了第 $d_i \in \{1,2,3\}$ 个部门，则该分配方案的满意度为 $\sum_{i=1}^{n} a_{i,d_i}$ 。

小 L 不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不存在一个部门被分配多于 $\frac{n}{2}$ 个新成员。你需要帮助小 L 求出，满足他要求的分配方案的满意度的最大值。

输入格式

本题包含多组测试数据。

输入的第一行包含一个正整数 $t$ ，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含一个正整数 $n$ ，表示新成员的数量。
第 $i+1$ ( $1 \leq i \leq n$ ) 行包含三个非负整数 $a_{i,1}, a_{i,2}, a_{i,3}$ ，分别表示第 $i$ 个新成员对第 $1,2,3$ 个部门的满意度。

输出格式

对于每组测试数据，输出一行一个非负整数，表示满足小 L 要求的分配方案的满意度的最大值。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

【样例 1 解释】

该样例共包含三组测试数据。

对于第一组测试数据，可以将四个新成员分别分配到第 $1,3,1,2$ 个部门，则三个部门的新成员数量分别为 $2,1,1$ ，均不超过 $\frac{4}{2} = 2$ ，满意度为 $4 + 4 + 5 + 5 = 18$ 。

对于第二组测试数据，可以将四个新成员分别分配到第 $1,1,2,2$ 个部门，则三个部门的新成员数量分别为 $2,2,0$ ，均不超过 $\frac{4}{2} = 2$ ，满意度为 $0 + 0 + 2 + 2 = 4$ 。

对于第三组测试数据，可以将两个新成员分别分配到第 $2,1$ 个部门，则三个部门的新成员数量分别为 $1,1,0$ ，均不超过 $\frac{2}{2} = 1$ ，满意度为 $9 + 4 = 13$ 。

【样例 2】

见选手目录下的 $\textbf{\textit{club/club2.in}}$ 与 $\textbf{\textit{club/club2.ans}}$ 。

该样例满足测试点 $3,4$ 的约束条件。

【样例 3】

见选手目录下的 $\textbf{\textit{club/club3.in}}$ 与 $\textbf{\textit{club/club3.ans}}$ 。

该样例满足测试点 $5 \sim 8$ 的约束条件。

【样例 4】

见选手目录下的 $\textbf{\textit{club/club4.in}}$ 与 $\textbf{\textit{club/club4.ans}}$ 。

该样例满足测试点 $9$ 的约束条件。

【样例 5】

见选手目录下的 $\textbf{\textit{club/club5.in}}$ 与 $\textbf{\textit{club/club5.ans}}$ 。

该样例满足测试点 $15,16$ 的约束条件。

【数据范围】

对于所有测试数据，保证：

$1 \leq t \leq 5$ ;
$2 \leq n \leq 10^5$ ，且 $n$ 为偶数;
对于所有 $1 \leq i \leq n$ ， $1 \leq j \leq 3$ ，均有 $0 \leq a_{i,j} \leq 2 \times 10^4$ 。

::cute-table{tuack}

测试点编号	$n=$	特殊性质
$1$	$2$	无
$2$	$4$	^
$3, 4$	$10$	^
$5 \sim 8$	$30$	^
$9$	$200$	B
$10, 11$	^	无
$12$	$10^5$	A
$13, 14$	^	B
$15, 16$	^	C
$17 \sim 20$	^	无

特殊性质 A：对于所有 $1 \leq i \leq n$ ，均有 $a_{i,2} = a_{i,3} = 0$ 。

特殊性质 B：对于所有 $1 \leq i \leq n$ ，均有 $a_{i,3} = 0$ 。

特殊性质 C：对于所有 $1 \leq i \leq n$ ， $1 \leq j \leq 3$ ， $a_{i,j}$ 均在 $[0, 2 \times 10^4]$ 中独立均匀随机生成。