参加过蓝桥杯的人都有过这种体验：一道贪心算法题摆在面前，看起来不过是排个序、取个最值，可真到赛场上，你排序的依据到底是什么，往往比写完代码本身难十倍。蓝桥杯里常考的那类“推公式”贪心题，不像暴力枚举那么直白，也不像动态规划那样有清晰的状态定义，它需要你现场把一个优化目标写成数学式子，再通过排序不等式、相邻交换这些手段，硬生生推出一个排序规则。换句话讲，推公式不是让你背模板，而是让你在考场上临时证明“为什么这么贪心是对的”。这篇文章就用三道经典例题——排队打水、国王游戏、耍杂技的牛——把推公式的完整思考路径拆给你看，照着这个思路练，再遇到同类题就知道该从哪里下手。

1. 推公式题的底层逻辑：为什么贪心需要“推公式”

1.1 直觉贪心很容易翻车

很多人学贪心时会记一堆“结论”，比如“取最小的”“选最大的”“先按端点排序”，然后做题时直接套。但在真正的竞赛题里，直觉往往是错的。

最典型的是删数问题：在一串数字中删掉 k 个数字，使剩下的数字按原顺序组成最小数。如果直觉是“每次删掉当前最大的数字”，你会得到完全错误的结果。比如 21435，要删两个数字，每次删最大数：先删 5 得 2143，再删 4 得 213。可正确做法是从高位往低位找第一个比右边数字大的数删掉：先删 2 得 1435，再删 4 得 135，最终得到 135，比 213 小得多。再比如一些找零钱问题，面额只有 1、5、11，要凑出 15，贪心取最大面额会得到 11+1+1+1+1 共 5 枚，而真正的最优解是 5+5+5 只要 3 枚。

这说明一个关键问题：竞赛里的贪心不是“看上去合理”，它必须有数学依据。推公式要解决的，恰恰就是给某个贪心策略一个可以被证明的、能落地的规则，而不是停留在“感觉应该这样排”的层面。

1.2 推公式的两大数学武器

推公式最常用的两个武器，一是排序不等式，二是相邻交换论证。

排序不等式说的是：如果有两组递增序列 a1 ≤ a2 ≤ ... ≤ an 和 b1 ≤ b2 ≤ ... ≤ bn，那么“顺序和”最大，“反序和”最小。翻译成人话就是：大的数配大的系数会放大结果，大的数配小的系数才能让总和变小。很多排队、分配类的贪心题，本质上都是在找一个“谁配谁”的匹配关系，排序不等式能直接告诉你答案。

相邻交换论证是更通吃的一类武器。它的核心思想是：假设存在一个最优排列，任取其中相邻的两个元素 x 和 y，我们尝试交换它们的位置。如果交换之后整体代价没有变差，那么说明“x 在 y 前面”不比“y 在 x 前面”差。把这个条件整理成一个不等式，往往就能得到一个简单的排序关键字，比如 a*b、w+s 之类。这一步不要求你证明整个排列，只需要盯着相邻两个元素看，复杂度低很多，思路也清晰很多。

1.3 相邻交换论证的标准套路

相邻交换论证在实践中可以归纳成固定四步：

1. 先写出代价函数，把题目的目标变成关于排列顺序的数学表达式，比如总和最小、最大值最小。
2. 取出相邻的两个元素 A、B，设它们前面所有元素的某个累加量为 S。
3. 分别计算 A、B 按两种顺序排列时的代价，得到两个表达式。
4. 比较两个表达式，消去相同的部分，化简出 A 排在 B 前面所需满足的不等式条件。

只要这个条件能被表示成一个可比较的关键值，这道题就被转化成了“按关键值排序”的简单形式。需要说明的是，相邻交换并不是所有贪心题的万能解法，但当你发现题目让一堆对象“排一个顺序”时，它几乎是最标准的思考路径。蓝桥杯省赛国赛里常见的活动安排、任务调度、叠罗汉这几种题型，基本都在这个框架里。

2. 第一道经典：排队打水，从求和式推出排序规则

2.1 题目与直觉

先看一道最入门的推公式题。有 n 个人排队打水，第 i 个人打水需要 t_i 分钟，每个人从开始排队到打完水为止的总耗时称为他的等待时间，问怎么排队能让所有人的等待时间总和最小。

这个题目很多人小学奥数就见过，答案也简单：打水时间短的人排在前面。但如果只是背这个结论，考试时把题目改一改，比如每个人打水时间要乘以一个权值，或者只算排队等待时间不算打水时间，很多人立刻就懵了。所以必须亲手把公式推一遍，理解这个结论是怎么来的。

2.2 代价函数怎么列

假设队伍顺序已经确定，第 i 个位置上的人打水时间为 x_i。第 i 个人的总耗时是前 i 个人打水时间之和，也就是 sum_{j=1}^{i} x_j。所有人的总等待时间 T 可以写成：

T = sum_{i=1}^{n} sum_{j=1}^{i} x_j = sum_{j=1}^{n} x_j * (n - j + 1)

这个式子的含义很直观：排在第 j 位的人，他的打水时间 x_j 会被后面 n-j+1 个人包含进等待时间里，所以被累加了 n-j+1 次。系数 n-j+1 从第 1 位的 n 一直递减到第 n 位的 1。

现在问题变成了：有一组固定的正系数 n、n-1、……、1，要把 x_1 到 x_n 这 n 个时间分别放上去，使得 Σ x_j * (n-j+1) 最小。根据排序不等式，大的数要配小的系数，小的数要配大的系数，所以应该把最小的打水时间放在第 1 位，最大的放在最后一位。于是得到结论：按 t_i 从小到大升序排列。

如果用相邻交换验证也一样：如果相邻两人 i 在前、j 在后，并且 x_i > x_j，那么交换两人的位置后，前面的系数差 (n-i+1) - (n-j+1) 是正数，交换后的总等待时间会减少，说明任何“前面耗时大、后面耗时小”的排列都不是最优的，最终必为升序。

2.3 完整代码与易错点

Python 实现非常短，排序后乘系数累加即可：

import sys def main(): data = list(map(int, sys.stdin.buffer.read().split())) n = data[0] t = data[1:] t.sort() ans = 0 for i, x in enumerate(t): ans += x * (n - i) print(ans) if __name__ == "__main__": main()

这里有一个容易错的地方：题目里“等待时间”是否包含自己打水的时间。如果包含，系数是 n-i；如果只算排队等待、不算自己打水时间，那第 i 个人的等待时间是前 i-1 个人的打水时间之和，最终式子变成 Σ x_j * (n-j)，系数从 n-1 到 0。两种情况下系数都是递减序列，结论仍然是升序，但累加的答案会差一组数，做题前一定要看清楚题面定义。

另一个坑是数据范围。n 最大可能到 1e5，单个打水时间到 1e5，总等待时间可能达到 1e15 级别，C++ 里必须用 long long，Java 里用 long，不要用 int 存答案。

3. 第二道经典：国王游戏，乘积比较里的高精度与排序规则

3.1 题目背景

国王游戏是 NOIP 2012 提高组的经典题，蓝桥杯历年省赛、国赛里类似“排列一组二元组后求最大值最小”的题经常能看到它的影子。题意是：国王和 n 个大臣站成一排，国王左手写着一个数 a0，每个大臣左右手各写一个正整数 a_i 和 b_i。每一个大臣获得的奖赏是：他前面所有人左手上的数乘起来，再除以他自己右手上的数，向下取整。国王希望所有大臣中奖赏最大的那个尽量小，问怎么给大臣排队。

很多人第一眼会猜按 a 排，或者按 b 排，或者按 a-b 排，但这几种直觉都是错的。正确答案是按 a_i * b_i 从小到大排。如果不亲手推一下，这个结论确实很难凭空想到。

3.2 相邻交换推导排序规则

设某相邻两个大臣为 i 和 i+1，他们前面所有大臣左手的乘积为 S，S 明显大于 0。考虑两种顺序。

顺序一：i 在前，i+1 在后。此时 i 的奖赏约为 S / b_i，i+1 的奖赏约为 S * a_i / b_{i+1}。这个顺序下的最大值就是这两个数里更大的那个。

顺序二：i+1 在前，i 在后。此时 i+1 的奖赏约为 S / b_{i+1}，i 的奖赏约为 S * a_{i+1} / b_i。最大值同理。

向下取整在这个推导里可以先放一边，因为取整不会改变分子分母大小关系的方向，排序规则由核心表达式决定，真正计算答案时再去 floor。比较两个最大值时，两边同时乘一个正数 b_i * b_{i+1} / S，可以消掉 S 和分母，化简为比较：

max(b_{i+1}, a_i * b_i) 与 max(b_i, a_{i+1} * b_{i+1})

如果 a_i * b_i ≤ a_{i+1} * b_{i+1}，因为 b_{i+1} ≤ a_{i+1} * b_{i+1}，所以：

max(b_{i+1}, a_i * b_i) ≤ a_{i+1} * b_{i+1} ≤ max(b_i, a_{i+1} * b_{i+1})

也就是说，当 a_i * b_i 较小时，i 排在 i+1 前面不会让最大值变大。于是排序关键字就是 a_i * b_i，升序排列。

还有一个细节必须注意：国王在最前面，位置固定，不能参与大臣的排序。但计算每个大臣奖赏时，前缀乘积要从国王左手那个数开始乘，国王自己虽然不拿奖，也会影响后面所有人的奖赏。

3.3 代码实现与高精度处理

国王游戏的最大特点是前缀乘积会爆炸式增长。所有数都是正整数，a 可以到 1e4，n 可以到 1000，前缀乘积可能变成一个上千位的天文数字。C++ 选手需要手写高精度乘法与除法，Java 可以用 BigInteger，Python 直接原生支持任意精度整数，写起来最舒服。

Python 实现：

import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) king_a = int(data[1]) king_b = int(data[2]) people = [] idx = 3 for _ in range(n): a = int(data[idx]) b = int(data[idx + 1]) idx += 2 people.append((a, b)) people.sort(key=lambda p: p[0] * p[1]) ans = 0 prod = king_a for a, b in people: cur = prod // b if cur > ans: ans = cur prod *= a print(ans) if __name__ == "__main__": main()

Java 关键片段：

// 注意排序比较用 long，避免 a*b 在 int 范围内溢出 Arrays.sort(people, (p, q) -> Long.compare(1L * p.a * p.b, 1L * q.a * q.b)); BigInteger prod = BigInteger.valueOf(kingA); BigInteger ans = BigInteger.ZERO; for (Node p : people) { BigInteger cur = prod.divide(BigInteger.valueOf(p.b)); if (cur.compareTo(ans) > 0) ans = cur; prod = prod.multiply(BigInteger.valueOf(p.a)); } System.out.println(ans);

C++ 组如果遇到这种题，最稳妥的方案是提前准备一套高精度板子，或者直接用 Python 提交。蓝桥杯的判题环境通常支持多种语言，没必要在 C++ 里硬写大整数乘除。

3.4 这题真正想考你的东西

国王游戏表面上是排序题，实际上考了三层：能不能从最值表达式推出排序规则，会不会处理大数运算，有没有意识到国王不能参与排序。三个点任何一个出错都会导致全盘失败。特别是考场上很多人推公式推到一半就放弃，凭“经验”随便定个关键字排序，样例能过，大数据一测就错。平时练这种题，一定要养成在草稿纸上把相邻两项拎出来写写的习惯。

4. 第三道经典：耍杂技的牛，极值型代价的推公式

4.1 题目描述

再看一道非常经典的叠罗汉问题。有 n 头牛，每头牛有重量 w_i 和承重能力 s_i，它们从上到下叠成一摞。每头牛的风险值定义是：它上面所有牛的体重之和减去它自己的承重能力，即超过承重多少。现在要调整牛的顺序，让所有牛中最大的风险值尽量小。

这道题的直觉也经常翻车。有人觉得重的牛应该放下面，有人觉得承重大的牛应该放下面，还有人觉得应该按重量减承重排序。正确答案是按 w_i + s_i 从小到大排序。这个和值如果不推导，光靠观察数据很难想到。

4.2 从风险表达式到排序关键字

设从上往下数，某头牛上面的牛总重量为 S_i，那么它自己的风险是 S_i - s_i。整个目标就是让所有的 S_i - s_i 中的最大值尽量小。

取相邻的两头牛，上面的牛记为 u，下面的牛记为 v。它们上面已经堆好的牛的总重量为 S。

顺序 A：u 在上，v 在下。此时 u 的风险 = S - s_u，v 的风险 = S + w_u - s_v，最大值 M_A = max(S - s_u, S + w_u - s_v)。

顺序 B：v 在上，u 在下。此时 v 的风险 = S - s_v，u 的风险 = S + w_v - s_u，最大值 M_B = max(S - s_v, S + w_v - s_u)。

要比较 M_A 和 M_B 谁更小，两边同时加一个相同的量 s_u + s_v - S，不影响大小关系。于是变成比较：

M_A' = max(s_v, w_u + s_u) M_B' = max(s_u, w_v + s_v)

注意到 w_u + s_u 和 w_v + s_v 是各自牛的“体重加承重”。如果 w_u + s_u ≤ w_v + s_v，那么 s_v ≤ w_v + s_v，所以：

M_A' = max(s_v, w_u + s_u) ≤ max(w_v + s_v, w_u + s_u) = w_v + s_v ≤ max(s_u, w_v + s_v) = M_B'

也就是说，w+s 值较小的牛放在上面时，相邻两牛的风险最大值不会更大。经过相邻交换论证，最终排序规则就是按 w_i + s_i 升序。

4.3 证明过程与答案初始化细节

上面这段推导在考场上不需要写得像数学论文那么完整，但核心的“把相邻两项的代价表达式列出来、消去相同项、得到排序条件”这三步一定要落在草稿纸上。很多同学看完题解觉得简单，自己动手时却总在某一步卡住，原因就是没亲自写过表达式。

这里有一个特别容易踩的坑：风险值允许是负数。第一头牛上面没有牛，它的风险是 0 - s_1，只要 s_1 为正，这就是个负数。如果求最大值时把答案初始化为 0，那么所有牛的风险都是负数的情况会被错误地输出成 0，而正确输出应该是一个负数。所以初始化答案必须用一个足够小的负数，比如 -1e18。

另一个坑出现在扫描阶段。排序完成后要重新扫一遍牛，先根据当前累计重量算出当前牛的风险、更新答案，再把这头牛的重量加进累计值里。顺序反了就全错。

4.4 代码实现

Python 实现：

import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) cows = [] idx = 1 for _ in range(n): w = int(data[idx]) s = int(data[idx + 1]) idx += 2 cows.append((w, s)) cows.sort(key=lambda x: x[0] + x[1]) ans = -10**18 total = 0 for w, s in cows: cur = total - s if cur > ans: ans = cur total += w print(ans) if __name__ == "__main__": main()

Java 或 C++ 实现的关键点在于答案初始化为 Long.MIN_VALUE / -0x3f3f3f3f3f3f3f3f，以及所有累计重量用 long。这道题的数据范围通常不会大到需要高精度，但用 int 仍然可能溢出。

5. 考场实战：推公式题的通用套路与避坑指南

5.1 四步法：从猜关键字到排序输出

综合上面三道题，推公式题完全可以套用一个固定流程：

1. 确定代价函数。先看题目要最小化什么，是求和、求最大值还是求乘积。
2. 猜一个排序方向。根据经验先猜一个关键字，比如按某个值升序或降序。
3. 相邻交换验证。把相邻两个对象拎出来，前面累计量记为 S，分别写两种顺序下的代价表达式，化简出排序条件。
4. 排序后扫描。按推导出的关键字排序，再线性扫一遍计算真正的答案。

怎么快速判断一道题是不是推公式题？特征非常明显：给一堆二元组或多元组，让你排列后求最大值最小、总和最小、某种极值，而且 n 的范围大到你根本不可能枚举全排列。只要满足这个特征，优先考虑相邻交换论证。

5.2 五个高频翻车点

竞赛里推公式题错的原因高度集中，我整理了一个速查表。

其中“用浮点比较”是个隐蔽问题。比如排序条件本质是比较 a/b 和 c/d 时，不要写成 a / b < c / d，因为浮点数可能丢精度，要写成 a * d < c * b。整数运算永远是最安全的。

5.3 和蓝桥杯真题怎么对应

蓝桥杯的题面虽然不像 ACM 那么复杂，但省赛里出现过大量“排序后求最值”的贪心题，比如活动安排、最小延迟任务调度、区间覆盖，本质上都是先证明一个局部规则再排序。刷历年真题时，看到题面里有“安排顺序”“排队”“调度”“叠放”这些字眼，就可以优先往相邻交换的方向想。

另外，想单独提一下删数问题。它和推公式里的排序型贪心不完全一样，它依靠的是“每一步删除一个局部逆序数字”的迭代思想，属于局部贪心推进的模型，同样需要证明每次决策不会让答案变差。考场上把这些模型分清楚，比死记模板重要得多。还有归并排序、KMP 这类经典算法是独立专题，推公式题主要服务的是贪心策略部分，别混在一起刷。

最后说点实在的

我个人在实际训练里最大的体会是，推公式题考的从来不是“会不会排序”，而是“能不能在几分钟内完成一次相邻交换的推导”。蓝桥杯赛场上压力很大，很多人第一反应是回忆看题解时记住的结论，题目一变就懵。我的建议是，平时练真题时，每道排序型贪心题都在草稿纸上把两个相邻元素拎出来写一遍，哪怕只是粗糙地推一下。坚持二十道题之后，你会形成一种条件反射，看到“最大化最小值”“最小值最大”这类关键词，就知道该去找相邻交换的不等式了。

最后再分享一个小习惯：推完公式之后，用极端数据自测一下。比如把所有 w 设成 1、所有 s 设成 1，或者把所有 a 设成 1、所有 b 设成 1，看排序结果和最终答案是否符合直觉。这种自测成本很低，却往往能拦住大部分因为排序规则写反、初始化错误导致的低级失误。推公式这件事，练的是手上的推导功夫和脑中的条件反射，多写几次，考场上的“灵光一现”其实都是平时演算的积累。