详解 CodeChef SALARY:用"全体加一、一人不加"操作将薪水序列均等化的最小步数问题
详解 CodeChef SALARY:用"全体加一、一人不加"操作将薪水序列均等化的最小步数问题
导读
本文围绕 code/online_challenges/src/codechef/SALARY/README.md 关联的 CodeChef 经典入门题 SALARY(Salary Inequality)展开:给定 N 名工人的薪水数组,唯一允许的操作是"选择一名工人,其余所有人薪水 +1",求使所有薪水相等所需的最少操作次数。文章将完整重述题意、推导出简洁的闭式答案、逐行剖析仓库中的 C 参考实现(含一个真实的编译陷阱),并给出可复现的测试用例与复杂度分析,帮助你彻底掌握这类"整体平移型"操作的贪心/数学建模思路。
一、问题重述:来自小主厨餐厅的薪水均等化
根据 SALARY 题目说明,故事的背景是:
- 小主厨(Little chief)经营着一家餐厅,共有 N 名工人;
- 第 i 名工人的薪水为 Wi(i = 1, 2, ..., N);
- 主厨希望让所有工人的薪水完全相等;
- 他只能使用一种操作:选择一名工人,让除该工人以外的所有其他工人薪水各 +1。
- 被选中的工人是"输家"(loser),是本次操作中唯一薪水不会增加的工人;
- 每一次操作可以更换"输家",即每轮选谁可以不同;
- 操作次数不限,但主厨很忙,希望最小化操作总次数,任务就是求出这个最小次数。
该题目属于 CodeChef 的入门级数学/贪心题,仓库收录于 code/online_challenges/src/codechef 目录(该目录汇集了 CodeChef 平台的 AMSGAME1、CARVANS、CLEANUP、FCTRL、GCD2 等大量题解),是练习"从操作不变量出发推导结论"的极佳素材。
二、核心观察:操作的本质是一种"整体平移"
初看这道题,最自然的想法是模拟操作、尝试各种策略。但直接模拟会立刻陷入"该选谁当输家"的组合困境。我们先把操作抽象化:
设当前薪水数组为 W[1..N],一次"选 x 当输家"的操作等价于:
所有元素先整体 +1(N 个元素全部增加 1)
再单独对 W[x] 减去 1
因为"除了 W[x] 之外的所有人都 +1" = "所有人 +1 之后,再单独把 W[x] 拉回 1 的增量"。
这个视角带来两个关键结论:
- 操作改变的是元素之间的差值。经过 k 次操作后,任意两名工人 i、j 的薪水差变为:
W[i] - W[j]减去(i 被选为输家的次数 − j 被选为输家的次数)。最终要使所有薪水相等,即所有差值归零。 - 每次操作总薪水增加 N − 1。设共执行 K 次操作,数组总和从
S = ΣWi变为N × T(T 为最终相等的薪水值),于是:N × T = S + K × (N - 1)
第二条给出了操作次数与最终薪水之间的代数约束,但它本身还不足以直接给出 K 的最小值——我们还需要确定 T 的下界。
三、数学推导:答案就是 Σ(Wi − minW)
关键的洞察在于:任何一次操作都会让最小值(或最小值之一)至少 +1——除非该最小值恰好是这一轮的"输家"。
更精确地说,设 m = min(W1, ..., WN)。观察任意一名原本薪水等于 m 的工人:
- 只要他被选为输家,他的薪水就不变;
- 只要他没被选为输家,他的薪水就 +1。
也就是说,这名最小值工人的薪水只会增加、永不减少。因此最终所有人的薪水 T 必然满足 T ≥ m。同时,T = m 是可达的(构造方法见第五节),所以:
最小操作次数 = Σ (Wi − m) = (ΣWi) − N × minW
即:把每个元素与全局最小值的差全部累加起来,就是答案。
直觉解释:要让最小值工人"追上"其他人,只能靠其他工人的薪水在每轮操作中不断 +1 而最小值工人"原地踏步"来缩小差距;每一轮最多让"最小薪水"这一水位保持不变(选择当前最小者当输家),而其他每个高于最小值的薪水每轮至多被"冻结"一次。整体上,所有超出最小值的薪水都必须通过操作"消失"掉,而一次操作恰好只能处理掉 N − 1 份"超出的薪水"(除输家外每人 +1 覆盖 1 份差距),因此总操作次数恰好等于所有差距之和。
以样例验证公式
W = [4, 2, 5]:m = 2,答案 = (4−2)+(2−2)+(5−2) = 2+0+3 = 5;W = [1, 1, 1, 1]:m = 1,答案 = 0 + 0 + 0 + 0 = 0(已经相等);W = [7](N = 1):m = 7,答案 = 0;W = [1, 2]:m = 1,答案 = 0 + 1 = 1。
这些结果与下文编译运行验证的测试输出完全一致。
四、仓库实现逐行解析:SALARY.c
仓库在 SALARY 题解目录 下提供了 C 参考实现 SALARY.c,核心思路完全对应上述公式。我们逐段解读:
#include<stdio.h>
int main()
{
int t;
scanf("%d", & t);
int T[t]; // 存储每组测试用例的答案
int i, j;
for (i = 0; i < t; ++i)
{
int n;
scanf("%d", & n); // 本组工人数 N
int A[n]; // VLA:变长数组,C99 起支持
int min = 32767; // 初始化最小值哨兵(大于约束上限即可)
for (j = 0; j < n; ++j)
{
scanf("%d", & A[j]);
if (A[j] < min)
{
min = A[j]; // 边读入边求全局最小值
}
}
int count = 0;
for (j = 0; j < n; ++j)
{
count += (A[j] - min); // 累加 Σ(Wi − min)
}
T[i] = count
}
for (i = 0; i < t; ++i)
{
printf("%d\n", T[i]);
}
return 0;
}
要点说明:
- 读入与最小值同步计算:第一遍循环在读入每个 A[j] 的同时维护
min,省去了单独扫描一遍数组求最小值的开销。初始哨兵取32767(2^15 − 1),只要题目约束中的薪水值小于该值即可正确工作(CodeChef 本题薪水为整数且量级远小于此);更稳健的写法是直接用INT_MAX(需#include <limits.h>)或用读入的第一个元素初始化。 - 两趟遍历、O(1) 额外空间:第二遍循环累加
A[j] - min,这正是推导出的闭式答案Σ(Wi − minW)。整个过程没有排序、没有贪心模拟、没有 DP,时间复杂度 O(N),空间上除存储答案的数组外为 O(1)。 - ⚠️ 仓库源码的一处编译陷阱:第 28 行
T<a href="https://link.gitcode.com/i/7982590970e9490d21d3e018c8e8506a" target="_blank">i] = count末尾缺少分号(紧接着的}处会触发 gcc 报错expected ';' before '}')。这是仓库原文件 [SALARY.c 中真实存在的笔误——本地编译验证时需补上分号(T[i] = count;)方可运行。阅读源码时留意这一点,避免照抄导致编译失败。 - 代码风格:该实现与仓库 C 编码规范指南 所倡导的 Kernel Normal Form(KNF)风格略有出入(如
scanf("%d", & t)的空格写法),但不影响正确性;提交竞赛时建议补充return 0;前的格式与变量声明的规范性。
五、为什么公式是最优的:下界证明与构造
为了严格说明"最少"二字,需要同时证明下界与可达性:
下界(至少需要 Σ(Wi − m) 次):任意一名原薪水为 m 的工人,其薪水从 m 增长到最终值 T。由于每次操作他要么 +1、要么不变,T − m 就是他总共被"非输家"选中的次数。要让所有人相等,最终 T 至少要等于其他人的最终薪水;而任何一次让这名工人 +1 的操作,同时也会让其他 N − 2 名(除他和输家外的)工人 +1。综合"总薪水增量 = K(N−1)"与"最终薪水 ≥ m"两个约束,可得 K ≥ Σ(Wi − m),即上述公式给出的是下界。
可达性(构造 K = Σ(Wi − m) 次操作的方案):执行如下策略——反复挑选当前薪水最小(或任意一名薪水仍高于全局初始最小值 m)的工人作为"输家"不做加法,对其余人各 +1。等价地,把"输家"身份轮流分配给那些还没有完成"补齐任务"的工人:对每名工人 i,他需要被"跳过加薪"的次数恰好是 Wi − m 次(这样才能让其他人在他不变的同时逐步追上)。由于 Σ(Wi − m) 恰好等于总操作次数,且每轮至少有一名"尚未补齐"的工人可以被选为输家,该策略可无冲突地持续执行直到所有差距归零,最终所有人的薪水都变为 m + K(对 N ≥ 2 恒成立;N = 1 时无需任何操作)。因此下界可达,公式即答案。
六、复杂度与数据规模
- 时间复杂度:每组测试用例 O(N),需要一次读入扫描求最小值 + 一次累加扫描。
- 空间复杂度:O(1)(不含结果输出数组),无需任何辅助数据结构。
- 典型约束:CodeChef 本题 T 组测试用例,N 与 Wi 均在常规 int 范围内;由于答案是"所有差值之和",当 N 与 Wi 较大时(例如 N 达 10^5、Wi 达 10^9 量级),建议使用
long long累加以防溢出——仓库的 int 版本在小数据量下正确,但扩展到大输入时应升级为 64 位整型。
对每个测试用例而言,整个求解是线性单遍扫描,在竞赛限制下性能绰绰有余。
七、实战:编译、运行与测试用例验证
仓库源码 SALARY.c 修正第 28 行的缺分号问题后即可编译运行:
# 在题解目录下编译(gcc 需支持 C99 变长数组)
gcc -O2 -o salary SALARY.c
# 标准输入格式:第一行 T,随后每组一行 N、一行 N 个薪水
以如下输入测试(覆盖多组场景):
6
3
4 2 5
1
7
5
1 1 1 1 1
2
1 2
2
2 1
4
10 10 10 10
预期输出依次为:
5
0
0
1
1
0
其中 [4,2,5] → 5 对应题目原始样例;[1,1,1,1]、[10,10,10,10] 输出 0 验证"已经相等时无需操作";[1,2] 与 [2,1] 均输出 1,验证公式与数组顺序无关。这些输出与公式 Σ(Wi − min) 逐一吻合,可作为自测用例。
八、思维延伸:把"加法"倒过来想
SALARY 这类题的一个通用套路是等价变换:将"每次除一人外全体 +1"等价为"每次把一个人的相对地位抬高"之后,问题立刻退化为最朴素的差分累加。类似地,若题目把操作改成"每次选一人,他的薪水 −1,其余人不变"(即反向操作),结论同样成立:因为原始操作的逆操作仍是同类结构,最优步数不变。理解这一点,有助于你在遇到"整体平移 + 单点冻结"模式的其他变体题(如 CodeChef 中同样依赖最小元素分析的 MNMX 等题)时,快速定位到"找全局极值 → 累加差距"的解法框架。
仓库 code/online_challenges/src/codechef 下还收录了多道同平台题目(含 MNMX 题解 等),可作为同类型思维训练的延伸阅读。
结语
SALARY 的价值在于用最少的代码揭示了一个深刻的结论:当操作是"全体平移 + 一人冻结"时,最小操作次数只由全局最小值决定,答案即所有元素与最小值的差之和。掌握"从操作不变量与上下界两端夹逼"的证明方法,比背下公式本身更重要——它能直接迁移到大量"等量化/均衡化"类问题。仓库中的 SALARY.c 提供了可直接验证的线性实现,修正分号笔误后即可亲手跑通上述全部测试用例。