题源链接：洛谷 P14361 [CSP-S 2025] 社团招新 / club

---

一、背景

在算法竞赛的贪心专题中，有一类问题表面上是"最大化总收益"，实际上考的是约束下的局部修复能力——先不管约束求最优，再把超标的部分"降级"到次优选择。CSP-S 2025 的这道社团招新题，就是这类问题的典型代表。

题目场景很真实：社团招新，每个新成员对三个部门有不同的满意度。目标是让总满意度最大，但有一个硬性约束：每个部门的人数不能超过总人数的一半。这个约束就像一把达摩克利斯之剑，悬在贪心策略的头顶——如果不加约束，所有人都会选自己最满意的部门，但某些热门部门可能会人满为患。

本文就从这道社团招新题出发，聊聊贪心降级策略的核心思想，以及鸽巢原理在约束分析中的巧妙应用。

---

二、核心思想

2.1 两步走：先全局最优，再局部修复

拿到这道题，很多选手的第一直觉可能是：这是一个动态规划问题，状态设计为 $dp[i][j][k]$ 表示前 $i$ 个人，三个部门分别有 $j,k,i-j-k$ 人的最大满意度。但当 $n=10^5$ 时，三维 DP 的状态空间达到 $O(n^3)$，完全不可行。

换个角度思考：如果没有人数约束，最优策略是什么？显然，每个人都选自己满意度最高的部门。这是 $O(n)$ 的贪心，非常简单。

那么，加上约束后会怎样？由于 $n$ 是偶数，每个部门的上限是 $n/2$。根据鸽巢原理，如果三个部门中有两个部门的人数都超过 $n/2$，那么总人数就会超过 $n$，这是不可能的。因此，最多只有一个部门会超标。

这个观察至关重要！它意味着我们只需要处理"一个部门超标"的情况，而不需要考虑复杂的组合约束。

两步走策略的特征：

• 第一步（无约束最优）：每个人选最优部门，计算总满意度
• 第二步（约束修复）：如果某部门超标，将部分成员"降级"到次优部门
• 降级原则：每次选择损失最小的成员降级，确保总满意度损失最少

2.2 为什么最多只有一个部门超标？

这是基于鸽巢原理的经典结论。

假设有两个部门的人数都超过 $n/2$，设为 $c_1>n/2$ 和 $c_2>n/2$。那么总人数至少为 $c_1+c_2>n/2+n/2=n$，矛盾（因为总人数恰好为 $n$）。

因此，最多只有一个部门的人数超过 $n/2$。这意味着：

• 如果无约束分配后没有部门超标，直接输出答案
• 如果有一个部门超标，只需要处理这个部门，其他部门不受影响

我们可以把这个过程想象成水库调度：

• 三个水库（部门）总容量为 $n$
• 每个水库最大容量为 $n/2$
• 水流（成员）自然流向最满意的水库
• 如果某个水库溢出，把溢出的水引向次优的水库
• 由于总容量限制，最多只有一个水库会溢出

2.3 损失最小化：降级的艺术

当部门 $pos$ 超标时，我们需要将 $num=cnt[pos]-n/2$ 个成员从 $pos$ 部门移出。移出后，这些成员需要选择其他部门（第二优或第三优）。

对于每个原本选择 $pos$ 的成员 $i$，如果强制他不选 $pos$，他的最小损失为：

$$d_i=\underset{j\ne pos}{\min }(a_{i,pos}-a_{i,j})$$

即最优选择 $pos$ 与次优选择之间的最小差距。我们要做的就是：在所有选择 $pos$ 的成员中，选出 $num$ 个 $d_i$ 最小的成员进行降级。

为什么选 $d_i$ 最小的？因为每次降级都会损失 $d_i$ 的满意度，我们要最小化总损失，自然应该优先降级"损失代价最小"的成员。

这就像裁员决策：公司需要裁员时，会优先裁掉"对业务影响最小"的员工（比如边缘岗位），而非核心骨干。这里的"损失"就是裁员对业务的负面影响。

---

三、算法模板

3.1 算法到底在干什么？——直觉解释

我们的算法是一台"智能分配器"：

1. 收集偏好：对于每个成员，找出他最满意的部门和次满意的部门
2. 无约束分配：让所有人都选最满意的部门，计算总满意度
3. 检查约束：统计每个部门的人数，看是否有人超标
4. 降级修复：如果某部门超标，收集该部门所有成员的"降级损失"，排序后取最小的几个进行降级
5. 输出结果：总满意度减去降级损失

整个过程就像高考志愿填报：

• 每个学生（成员）有三个志愿（部门），有对应的分数（满意度）
• 先按第一志愿录取（无约束最优）
• 如果某专业（部门）超额，把分数最低的考生调剂到第二志愿（降级）
• 调剂时优先选择"与第一志愿分差最小"的考生（损失最小）

3.2 万能模板 —— 伪代码 + 实战代码

伪代码：

function 带约束分配(成员[1..n], 部门[1..3]):
    ans = 0
    cnt[1..3] = 0
    losses = []

    for each member i:
        max_val = max(a[i][1], a[i][2], a[i][3])
        max_idx = argmax(a[i][1..3])
        d = min(a[i][max_idx] - a[i][j]) for j != max_idx

        ans += max_val
        cnt[max_idx]++
        record (max_idx, d) for member i

    pos = argmax(cnt[1..3])
    if cnt[pos] <= n/2:
        return ans

    // 收集所有选择 pos 的成员的损失
    for each member i with max_idx == pos:
        losses.append(d_i)

    sort(losses, 升序)
    num = cnt[pos] - n/2

    for i = 1 to num:
        ans -= losses[i]

    return ans

实战代码（通用模板）：

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

const int N = 100005;

struct Member
{
    int maxx;
    int idx;
    int d;
};

int t, n;
int a[4];
Member sn[N];
int cnt[4];
int b[N];

int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        int ans = 0;
        memset(cnt, 0, sizeof(cnt));

        for (int i = 1; i <= n; i++)
        {
            cin >> a[1] >> a[2] >> a[3];
            sn[i].maxx = a[1];
            sn[i].idx = 1;
            sn[i].d = 1e9;

            for (int j = 2; j <= 3; j++)
                if (a[j] > sn[i].maxx)
                {
                    sn[i].maxx = a[j];
                    sn[i].idx = j;
                }

            for (int j = 1; j <= 3; j++)
                if (j != sn[i].idx)
                    sn[i].d = min(sn[i].d, sn[i].maxx - a[j]);

            ans += sn[i].maxx;
            cnt[sn[i].idx]++;
        }

        int pos = 1;
        for (int i = 2; i <= 3; i++)
            if (cnt[i] > cnt[pos])
                pos = i;

        if (cnt[pos] <= n / 2)
        {
            cout << ans << endl;
            continue;
        }

        int len = 0;
        for (int i = 1; i <= n; i++)
            if (sn[i].idx == pos)
                b[++len] = sn[i].d;

        sort(b + 1, b + 1 + len);
        int num = cnt[pos] - n / 2;

        for (int i = 1; i <= num; i++)
            ans -= b[i];

        cout << ans << endl;
    }
    return 0;
}

3.3 例题实现 —— 本题完整代码

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

const int N = 100005;  // 定义最大数组长度

// 结构体：存储每个成员的信息
struct Node
{
    int maxx;  // 三个满意度中的最大值
    int idx;   // 最大值所在的部门索引（1,2,3）
    int d;     // 最大值与次大值的最小差值（降级损失）
} sn[N];       // 存储每个成员的数据

int t;         // 测试数据组数
int n;         // 每个测试用例的成员数量
int a[4];      // 临时存储输入的三个满意度
int ans;       // 当前测试用例的总满意度
int cnt[4];    // 统计每个部门作为最优选择的人数
int b[N];      // 临时数组，存储需要调整的降级损失

int main()
{
    // 输入测试数据组数
    cin >> t;

    // 处理每组测试数据
    while (t--)
    {
        // 初始化变量
        ans = 0;
        memset(cnt, 0, sizeof(cnt));  // 清空部门人数计数器

        // 输入成员数量
        cin >> n;

        // 处理每个成员的信息
        for (int i = 1; i <= n; i++)
        {
            // 输入三个部门的满意度
            cin >> a[1] >> a[2] >> a[3];

            // 初始化当前成员的数据
            sn[i].maxx = a[1];  // 假设第1个部门满意度最高
            sn[i].idx = 1;      // 最优部门索引为1
            sn[i].d = 1e9;      // 初始化降级损失为极大值

            // 找出满意度最高的部门
            for (int j = 2; j <= 3; j++)
            {
                if (a[j] > sn[i].maxx)
                {
                    sn[i].maxx = a[j];
                    sn[i].idx = j;
                }
            }

            // 计算最小降级损失（最优与次优的最小差距）
            for (int j = 1; j <= 3; j++)
            {
                if (j == sn[i].idx)  // 跳过最优部门本身
                    continue;
                sn[i].d = min(sn[i].d, sn[i].maxx - a[j]);
            }

            // 累加无约束最优总满意度
            ans += sn[i].maxx;

            // 统计该最优部门的人数
            cnt[sn[i].idx]++;
        }

        // 找出人数最多的部门
        int pos = 1;
        for (int i = 2; i <= 3; i++)
        {
            if (cnt[i] > cnt[pos])
            {
                pos = i;
            }
        }

        // 检查是否需要调整（如果某部门人数超过n/2）
        if (cnt[pos] <= n / 2)
        {
            // 无部门超标，直接输出无约束最优总满意度
            cout << ans << endl;
        }
        else
        {
            // 部门pos超标，需要降级部分成员
            int len = 0;  // 需要调整的成员数量

            // 收集所有选择部门pos的成员的降级损失
            for (int i = 1; i <= n; i++)
            {
                if (sn[i].idx == pos)
                {
                    len++;
                    b[len] = sn[i].d;  // 存储降级损失
                }
            }

            // 对降级损失进行升序排序（优先降级损失最小的成员）
            sort(b + 1, b + 1 + len);

            // 计算需要降级的成员数量
            int num = cnt[pos] - n / 2;

            // 从总满意度中减去最小的num个降级损失
            for (int i = 1; i <= num; i++)
            {
                ans -= b[i];
            }

            // 输出调整后的总满意度
            cout << ans << endl;
        }
    }

    return 0;
}

3.4 对比实现 —— 贪心降级 vs 动态规划

本题也可以用动态规划解决，但贪心降级更优：

方案	核心思想	时间复杂度	适用场景
贪心降级（本题做法）	先最优再修复，损失最小化	$O(n\log n)$	本题场景，最简洁高效
三维 DP	$dp[i][j][k]$ 表示前 $i$ 人，三部门人数为 $j,k$ 的最大满意度	$O(n^3)$	$n$ 很小（$\le 100$）
网络流	建模为带容量限制的最大权分配	多项式但复杂	需要通用解法时
整数规划	建模为整数线性规划	指数级	理论分析

对于本题，$n$ 可以达到 $10^5$，贪心降级的 $O(n\log n)$ 完全够用，而 DP 的 $O(n^3)$ 完全不可行。贪心策略的正确性依赖于鸽巢原理保证的"最多一个部门超标"。

3.5 变体清单 —— 常见变形

变体类型	题目描述	关键变化	解法调整
$k$ 个部门	部门数从 $3$ 变为 $k$	部门数变化	鸽巢原理仍保证最多 $k-2$ 个部门超标，但可能需要更复杂的降级策略
容量不同	每个部门有不同的容量上限	约束变化	找出超标的部门，按容量差计算降级数量
成员有优先级	某些成员必须优先满足	增加优先级约束	先处理优先成员，再处理普通成员
多次调整	允许成员在不同部门间多次调整	目标变化	可能需要更复杂的迭代优化
满意度为负数	某些部门满意度为负	数据变化	成员可能宁愿不被分配，需要特殊处理
求具体分配方案	输出每个成员的部门分配	目标变化	记录降级决策，回溯输出
在线添加成员	成员逐个加入，动态维护	动态变化	需要支持动态插入的数据结构

3.6 什么时候不能用？——边界条件和反例

贪心降级策略虽然高效，但也有需要注意的边界：

• $n$ 为奇数：题目保证 $n$ 为偶数。如果 $n$ 为奇数，上限 $\lfloor n/2\rfloor$ 可能导致两个部门同时达到上限（如 $n=5$，两个部门各 $2$ 人，第三个部门 $1$ 人），此时鸽巢原理的结论需要调整。
• 所有成员满意度相同：如 $a_{i,j}=1$ 对所有 $i,j$。此时任意分配方案满意度都相同，贪心降级仍然正确（损失为 $0$）。
• 某部门满意度全为 $0$：如果某部门对所有成员的满意度都是 $0$，它自然不会成为最优选择，但如果其他部门都超标，可能需要强制分配成员到该部门（此时需要更复杂的处理）。
• $d_i=0$ 的情况：如果某成员对两个部门的满意度相同，降级损失为 $0$。这意味着降级不会影响总满意度，贪心策略仍然正确（优先降级这些成员）。
• 多个部门同时达到上限：当 $n$ 为偶数时，可能出现两个部门恰好都达到 $n/2$ 的情况（如 $n=4$，两个部门各 $2$ 人）。此时没有部门超标，直接输出答案即可。

---

四、底层逻辑

4.1 为什么贪心降级策略能得到最优解？

这是基于交换论证的经典证明。

设无约束最优分配后，部门 $pos$ 超标，需要降级 $num$ 个成员。设贪心策略降级的成员集合为 G = { g 1 , g 2 , … , g n u m } G = \{g_1, g_2, \ldots, g_{num}\} G={g1​,g2​,…,gnum​}，其损失为 $d_{g_1}\le d_{g_2}\le \cdots \le d_{g_{num}}$（排序后的前 $num$ 个最小损失）。

假设存在另一个最优降级方案，选择了成员集合 O = { o 1 , o 2 , … , o n u m } O = \{o_1, o_2, \ldots, o_{num}\} O={o1​,o2​,…,onum​}，其总损失更小。由于 $G$ 是损失最小的 $num$ 个成员，对于任意 $o_j\in O$，如果 $o_j\notin G$，则 $d_{o_j}\ge d_{g_{num}}$（否则 $o_j$ 会被选入 $G$）。

因此，${\sum }_{o\in O}{d}_o\ge {\sum }_{g\in G}{d}_g$，即贪心策略的总损失最小。由于无约束最优总满意度固定，损失最小即总满意度最大。

这个证明的优雅之处在于：它不需要知道最优解长什么样，只需要证明贪心选择的局部最优性就能推导全局最优。

4.2 与经典问题的对比

这道题和经典的分配问题家族有密切联系：

问题	约束条件	目标	典型解法
本题：带容量约束分配	每部门人数 $\le n/2$	最大总满意度	贪心降级
指派问题	每人恰好分配到一个任务	最大/最小总权值	匈牙利算法 $O(n^3)$
负载均衡	每个服务器负载均衡	最小化最大负载	贪心或近似算法
背包问题	容量限制	最大价值	动态规划
网络流分配	边容量限制	最大流	最大流算法

可以看到，贪心降级是处理"带简单容量约束的分配问题"的高效策略，而复杂的约束通常需要更高级的算法（如网络流、整数规划）。

4.3 隐含约束的分析

题目中有几个容易被忽略但至关重要的细节：

• $n$ 为偶数：这是鸽巢原理成立的关键。如果 $n$ 为奇数，最多只有一个部门超过 $\lfloor n/2\rfloor$，但可能有两个部门恰好等于 $\lfloor n/2\rfloor$，此时需要更细致的分析。
• 满意度为非负整数：保证了总满意度不会为负，且降级损失 $d_i\ge 0$。
• 三个部门：部门数固定为 $3$，这使得鸽巢原理的应用非常直接。如果部门数更多，分析会复杂一些。
• 多组测试数据：$t$ 组数据，每组需要独立处理，注意清空数组。

---

五、决策表

面对"带容量约束的分配优化"类问题，如何根据约束复杂度快速选型？

场景特征	推荐方案	时间复杂度	备注
简单容量约束（如上限 $n/2$），部门数少	贪心降级	$O(n\log n)$	本题场景，最简洁
复杂容量约束，部门数多	网络流 / 整数规划	多项式或伪多项式	需要通用解法
成员数少（$n\le 100$）	动态规划	$O(n^k)$（$k$ 为部门数）	状态设计直接
需要输出具体分配	记录决策路径	同主算法	增加路径数组
在线动态调整	贪心 + 数据结构维护	$O(\log n)$ 每次	需要支持动态操作

一句话总结：简单约束想降级，复杂约束想流，数据小想 DP，在线想数据结构。

---

六、工程视角

贪心降级策略的思想在实际工程中有着广泛的应用：

1. 负载均衡与资源调度：在云计算中，任务需要分配到多个服务器，每个服务器有容量上限。当某个服务器过载时，将部分任务迁移到负载较轻的服务器，优先迁移"迁移成本最小"的任务（如内存占用小、依赖少的任务）。这与本题的降级策略完全一致。

2. 广告竞价与预算分配：在广告投放中，广告主有预算上限，需要在多个广告位之间分配预算。当某个广告位的消耗超过预算时，将部分预算转移到次优的广告位，优先转移"转化率损失最小"的预算。

3. 课程选课系统：在大学选课系统中，每门课有容量限制。当某门热门课超额时，将部分学生调剂到次优的课程，优先调剂"课程满意度差距最小"的学生（比如第一志愿和第二志愿都是同一类课程的学生）。

4. 供应链库存管理：在供应链中，每个仓库有容量限制。当某个仓库库存超过上限时，将部分货物转移到其他仓库，优先转移"运输成本最低"的货物。

---

七、小结

本文从一道 CSP-S 真题出发，探讨了带约束分配的贪心降级策略问题。

核心认知可以总结为：

当约束是简单的容量上限时，先求无约束最优解，再通过"损失最小化"的贪心降级修复约束违反，往往比直接求解约束优化问题更高效；鸽巢原理是分析约束冲突的关键工具。

用公式化的语言概括：

$$\text{答案}=\sum _{i=1}^n\underset{j}{\max }{a}_{i,j}-\sum _{k=1}^{num}{d}_{(k)}$$

其中 $num=\max (0,{\max }_{j}cnt[j]-n/2)$ 为需要降级的成员数，$d_{(k)}$ 为选择超标部门的成员中第 $k$ 小的降级损失。

这道题教会我们的，不仅是如何写排序和结构体，更是一种**“先放松约束再修复”**的工程思维：在算法竞赛中，很多带约束的优化问题，直接求解约束版本会非常复杂。但如果约束是"松的"（即大部分情况下不会违反），先求无约束最优解，再局部修复违反约束的部分，往往是最高效的策略。这种"先易后难、局部修复"的思维方式，在处理实际工程问题时同样适用。

---

如果这篇文章对你有帮助，欢迎点赞收藏！有任何问题欢迎在评论区留言交流。