[CSP-S 2025] 社团招新题解

一、题干信息解读

有 (n) 个新成员（(n) 为偶数），需要分配到 3 个部门。
第 (i) 个成员对第 (j) 个部门的满意度为 (a_{i,j})（非负整数）。
要求：任意一个部门的人数不能超过 (n/2)。
求所有合法分配方案中，满意度总和的最大值。

多组测试数据，(t \le 5)，(n \le 10^5)，(0 \le a_{i,j} \le 2 \times 10^4)。

---

二、整体做题思路

1. 无限制时的最优解

如果没有人数限制，每个人当然选择自己满意度最高的部门。
对每个成员 (i)，令：

[
\text{mx}i = \max(a{i,1}, a_{i,2}, a_{i,3})
]

并记录他选择的部门。
把所有 (\text{mx}_i) 加起来，得到理论最大满意度 sum_max。

2. 限制条件分析

令 (m = n/2)。三个部门的人数上限都是 (m)。
总人数 (n = 2m)。

关键观察：最多只有一个部门的人数会超过 (m)。
证明：假设有两个部门都超过 (m)，那么它们的人数至少都是 (m+1)，两个加起来就是 (2m+2 > n)，矛盾。
所以，如果初始选择最大满意度后有人数超限，那一定只有一个部门超限。

3. 调整策略

设初始选择后，部门 (A) 的人数 cnt[A] > m，超出人数为：

[
k = \text{cnt}[A] - m
]

我们需要从原本选择部门 (A) 的成员中，移出 (k) 个人到另外两个部门（设为 (B) 和 (C)），使得总满意度下降最少。

对于原本选择 (A) 的成员 (i)，如果他改选 (B)，满意度损失为：

[
\text{loss}B = a{i,A} - a_{i,B}
]

改选 (C) 的损失为：

[
\text{loss}C = a{i,A} - a_{i,C}
]

我们当然希望移出的人损失越小越好，所以对每个原本选 (A) 的成员，取他改选 (B) 或 (C) 的较小损失：

[
\text{loss}i = \min(a{i,A} - a_{i,B},\ a_{i,A} - a_{i,C})
]

把所有这样的 loss_i 收集起来，从小到大排序，取前 (k) 个相加，得到最小总损失 loss_sum。

最终答案：

[
\text{answer} = \text{sum_max} - \text{loss_sum}
]

4. 为什么移出后不会导致其他部门超限？

初始时，另外两个部门 (B) 和 (C) 的人数分别为 (c_B, c_C)，且：

[
c_B + c_C = n - \text{cnt}[A]
]

因为 (\text{cnt}[A] > m)，所以：

[
c_B + c_C < n - m = m
]

我们从 (A) 移出 (k = \text{cnt}[A] - m) 人，分配到 (B) 和 (C)。
新的总人数为：

[
(c_B + c_C) + k = (n - \text{cnt}[A]) + (\text{cnt}[A] - m) = n - m = m
]

也就是说，调整后 (B) 和 (C) 两个部门的总人数恰好是 (m)。
而每个部门的上限也是 (m)，所以无论这 (m) 个人怎么分到 (B) 和 (C)，每个部门都不会超过 (m)。
因此我们不需要再关心 (B) 和 (C) 的具体分配，只需保证总损失最小即可。

---

三、题目中的难点和注意事项

1. 超限部门最多只有一个：这是解题的关键，避免了复杂的动态规划或网络流。
2. 移出损失的计算：对于原本选择超限部门的人，只需考虑改到另外两个部门的损失，取较小值。
3. 贪心选择：选择损失最小的 (k) 个人移出，可以用排序解决。
4. 数据范围：(n \le 10^5)，总满意度可能达到 (2 \times 10^9)，需要用 long long。
5. 多组测试数据：注意每组之间清空数组和变量。

---

四、标准程序（C++）

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

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        int m = n / 2;
        vector<array<int, 3>> a(n);
        vector<int> choice(n);
        long long sum_max = 0;
        int cnt[3] = {0};

        for (int i = 0; i < n; i++) {
            int x, y, z;
            scanf("%d %d %d", &x, &y, &z);
            a[i] = {x, y, z};

            // 找满意度最高的部门
            int mx = x, idx = 0;
            if (y > mx) { mx = y; idx = 1; }
            if (z > mx) { mx = z; idx = 2; }

            choice[i] = idx;
            cnt[idx]++;
            sum_max += mx;
        }

        int over = -1;
        for (int j = 0; j < 3; j++) {
            if (cnt[j] > m) {
                over = j;
                break;
            }
        }

        if (over == -1) {
            printf("%lld\n", sum_max);
            continue;
        }

        int k = cnt[over] - m; // 需要移出的人数
        vector<int> losses;
        losses.reserve(cnt[over]);

        for (int i = 0; i < n; i++) {
            if (choice[i] == over) {
                int o1 = (over + 1) % 3;
                int o2 = (over + 2) % 3;
                int loss1 = a[i][over] - a[i][o1];
                int loss2 = a[i][over] - a[i][o2];
                losses.push_back(min(loss1, loss2));
            }
        }

        sort(losses.begin(), losses.end());
        long long loss_sum = 0;
        for (int i = 0; i < k; i++) {
            loss_sum += losses[i];
        }

        printf("%lld\n", sum_max - loss_sum);
    }
    return 0;
}

---

五、时间与空间复杂度分析

• 时间复杂度：
  每个成员处理一次，找最大值 (O(1))。
  收集损失并排序：最多 (n) 个损失，排序 (O(n \log n))。
  总时间复杂度：(O(n \log n)) 每组，(t \le 5)，(n \le 10^5)，完全可以在 1 秒内运行完成。

• 空间复杂度：
  存储每个成员的三个满意度 (O(n))，损失数组 (O(n))，总空间 (O(n))。
  对于 (n = 10^5)，内存占用很小，远低于 1024 MB 限制。

---

六、样例解释

样例 1

3
4
4 2 1
3 2 4
5 3 4
3 5 1
4
0 1 0
0 1 0
0 2 0
0 2 0
2
10 9 8
4 0 0

第一组：
(n=4, m=2)。
初始最高选择：成员1→部门1(4)，成员2→部门3(4)，成员3→部门1(5)，成员4→部门2(5)。
各部门人数：部门1=2，部门2=1，部门3=1，均 ≤ 2。
sum_max = 4+4+5+5 = 18。输出 18。

第二组：
(n=4, m=2)。
所有人最高都是部门2，满意度分别为 1,1,2,2。
部门2人数 = 4 > 2，超限，(k = 4-2 = 2)。
原本选部门2的人损失：
成员1：改1损失1，改3损失1 → 1
成员2：改1损失1，改3损失1 → 1
成员3：改1损失2，改3损失2 → 2
成员4：改1损失2，改3损失2 → 2
损失排序：1,1,2,2，取前2个：1+1=2。
sum_max = 6，答案 = 6 - 2 = 4。输出 4。

第三组：
(n=2, m=1)。
成员1→部门1(10)，成员2→部门1(4)。
部门1人数 = 2 > 1，超限，(k = 1)。
损失：成员1改2损失1，改3损失2 → min=1；成员2改2损失4，改3损失4 → min=4。
取前1个：1。
sum_max = 14，答案 = 14 - 1 = 13。输出 13。

与题目输出完全一致。

---

七、总结

本题的核心是发现“最多只有一个部门超限”，然后通过贪心选择损失最小的成员进行调整。
代码实现简单，复杂度优秀，是一道典型的贪心题。
掌握这种“先取最优，再局部调整”的思路，对解决类似问题很有帮助。