参加过蓝桥杯的人都有过这种体验一道贪心算法题摆在面前看起来不过是排个序、取个最值可真到赛场上你排序的依据到底是什么往往比写完代码本身难十倍。蓝桥杯里常考的那类“推公式”贪心题不像暴力枚举那么直白也不像动态规划那样有清晰的状态定义它需要你现场把一个优化目标写成数学式子再通过排序不等式、相邻交换这些手段硬生生推出一个排序规则。换句话讲推公式不是让你背模板而是让你在考场上临时证明“为什么这么贪心是对的”。这篇文章就用三道经典例题——排队打水、国王游戏、耍杂技的牛——把推公式的完整思考路径拆给你看照着这个思路练再遇到同类题就知道该从哪里下手。1. 推公式题的底层逻辑为什么贪心需要“推公式”1.1 直觉贪心很容易翻车很多人学贪心时会记一堆“结论”比如“取最小的”“选最大的”“先按端点排序”然后做题时直接套。但在真正的竞赛题里直觉往往是错的。最典型的是删数问题在一串数字中删掉 k 个数字使剩下的数字按原顺序组成最小数。如果直觉是“每次删掉当前最大的数字”你会得到完全错误的结果。比如 21435要删两个数字每次删最大数先删 5 得 2143再删 4 得 213。可正确做法是从高位往低位找第一个比右边数字大的数删掉先删 2 得 1435再删 4 得 135最终得到 135比 213 小得多。再比如一些找零钱问题面额只有 1、5、11要凑出 15贪心取最大面额会得到 111111 共 5 枚而真正的最优解是 555 只要 3 枚。这说明一个关键问题竞赛里的贪心不是“看上去合理”它必须有数学依据。推公式要解决的恰恰就是给某个贪心策略一个可以被证明的、能落地的规则而不是停留在“感觉应该这样排”的层面。1.2 推公式的两大数学武器推公式最常用的两个武器一是排序不等式二是相邻交换论证。排序不等式说的是如果有两组递增序列 a1 ≤ a2 ≤ ... ≤ an 和 b1 ≤ b2 ≤ ... ≤ bn那么“顺序和”最大“反序和”最小。翻译成人话就是大的数配大的系数会放大结果大的数配小的系数才能让总和变小。很多排队、分配类的贪心题本质上都是在找一个“谁配谁”的匹配关系排序不等式能直接告诉你答案。相邻交换论证是更通吃的一类武器。它的核心思想是假设存在一个最优排列任取其中相邻的两个元素 x 和 y我们尝试交换它们的位置。如果交换之后整体代价没有变差那么说明“x 在 y 前面”不比“y 在 x 前面”差。把这个条件整理成一个不等式往往就能得到一个简单的排序关键字比如 a*b、ws 之类。这一步不要求你证明整个排列只需要盯着相邻两个元素看复杂度低很多思路也清晰很多。1.3 相邻交换论证的标准套路相邻交换论证在实践中可以归纳成固定四步先写出代价函数把题目的目标变成关于排列顺序的数学表达式比如总和最小、最大值最小。取出相邻的两个元素 A、B设它们前面所有元素的某个累加量为 S。分别计算 A、B 按两种顺序排列时的代价得到两个表达式。比较两个表达式消去相同的部分化简出 A 排在 B 前面所需满足的不等式条件。只要这个条件能被表示成一个可比较的关键值这道题就被转化成了“按关键值排序”的简单形式。需要说明的是相邻交换并不是所有贪心题的万能解法但当你发现题目让一堆对象“排一个顺序”时它几乎是最标准的思考路径。蓝桥杯省赛国赛里常见的活动安排、任务调度、叠罗汉这几种题型基本都在这个框架里。2. 第一道经典排队打水从求和式推出排序规则2.1 题目与直觉先看一道最入门的推公式题。有 n 个人排队打水第 i 个人打水需要 t_i 分钟每个人从开始排队到打完水为止的总耗时称为他的等待时间问怎么排队能让所有人的等待时间总和最小。这个题目很多人小学奥数就见过答案也简单打水时间短的人排在前面。但如果只是背这个结论考试时把题目改一改比如每个人打水时间要乘以一个权值或者只算排队等待时间不算打水时间很多人立刻就懵了。所以必须亲手把公式推一遍理解这个结论是怎么来的。2.2 代价函数怎么列假设队伍顺序已经确定第 i 个位置上的人打水时间为 x_i。第 i 个人的总耗时是前 i 个人打水时间之和也就是 sum_{j1}^{i} x_j。所有人的总等待时间 T 可以写成T sum_{i1}^{n} sum_{j1}^{i} x_j sum_{j1}^{n} x_j * (n - j 1)这个式子的含义很直观排在第 j 位的人他的打水时间 x_j 会被后面 n-j1 个人包含进等待时间里所以被累加了 n-j1 次。系数 n-j1 从第 1 位的 n 一直递减到第 n 位的 1。现在问题变成了有一组固定的正系数 n、n-1、……、1要把 x_1 到 x_n 这 n 个时间分别放上去使得 Σ x_j * (n-j1) 最小。根据排序不等式大的数要配小的系数小的数要配大的系数所以应该把最小的打水时间放在第 1 位最大的放在最后一位。于是得到结论按 t_i 从小到大升序排列。如果用相邻交换验证也一样如果相邻两人 i 在前、j 在后并且 x_i x_j那么交换两人的位置后前面的系数差 (n-i1) - (n-j1) 是正数交换后的总等待时间会减少说明任何“前面耗时大、后面耗时小”的排列都不是最优的最终必为升序。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 longJava 里用 long不要用 int 存答案。3. 第二道经典国王游戏乘积比较里的高精度与排序规则3.1 题目背景国王游戏是 NOIP 2012 提高组的经典题蓝桥杯历年省赛、国赛里类似“排列一组二元组后求最大值最小”的题经常能看到它的影子。题意是国王和 n 个大臣站成一排国王左手写着一个数 a0每个大臣左右手各写一个正整数 a_i 和 b_i。每一个大臣获得的奖赏是他前面所有人左手上的数乘起来再除以他自己右手上的数向下取整。国王希望所有大臣中奖赏最大的那个尽量小问怎么给大臣排队。很多人第一眼会猜按 a 排或者按 b 排或者按 a-b 排但这几种直觉都是错的。正确答案是按 a_i * b_i 从小到大排。如果不亲手推一下这个结论确实很难凭空想到。3.2 相邻交换推导排序规则设某相邻两个大臣为 i 和 i1他们前面所有大臣左手的乘积为 SS 明显大于 0。考虑两种顺序。顺序一i 在前i1 在后。此时 i 的奖赏约为 S / b_ii1 的奖赏约为 S * a_i / b_{i1}。这个顺序下的最大值就是这两个数里更大的那个。顺序二i1 在前i 在后。此时 i1 的奖赏约为 S / b_{i1}i 的奖赏约为 S * a_{i1} / b_i。最大值同理。向下取整在这个推导里可以先放一边因为取整不会改变分子分母大小关系的方向排序规则由核心表达式决定真正计算答案时再去 floor。比较两个最大值时两边同时乘一个正数 b_i * b_{i1} / S可以消掉 S 和分母化简为比较max(b_{i1}, a_i * b_i) 与 max(b_i, a_{i1} * b_{i1})如果 a_i * b_i ≤ a_{i1} * b_{i1}因为 b_{i1} ≤ a_{i1} * b_{i1}所以max(b_{i1}, a_i * b_i) ≤ a_{i1} * b_{i1} ≤ max(b_i, a_{i1} * b_{i1})也就是说当 a_i * b_i 较小时i 排在 i1 前面不会让最大值变大。于是排序关键字就是 a_i * b_i升序排列。还有一个细节必须注意国王在最前面位置固定不能参与大臣的排序。但计算每个大臣奖赏时前缀乘积要从国王左手那个数开始乘国王自己虽然不拿奖也会影响后面所有人的奖赏。3.3 代码实现与高精度处理国王游戏的最大特点是前缀乘积会爆炸式增长。所有数都是正整数a 可以到 1e4n 可以到 1000前缀乘积可能变成一个上千位的天文数字。C 选手需要手写高精度乘法与除法Java 可以用 BigIntegerPython 直接原生支持任意精度整数写起来最舒服。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(keylambda 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。顺序 Au 在上v 在下。此时 u 的风险 S - s_uv 的风险 S w_u - s_v最大值 M_A max(S - s_u, S w_u - s_v)。顺序 Bv 在上u 在下。此时 v 的风险 S - s_vu 的风险 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也就是说ws 值较小的牛放在上面时相邻两牛的风险最大值不会更大。经过相邻交换论证最终排序规则就是按 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(keylambda 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 四步法从猜关键字到排序输出综合上面三道题推公式题完全可以套用一个固定流程确定代价函数。先看题目要最小化什么是求和、求最大值还是求乘积。猜一个排序方向。根据经验先猜一个关键字比如按某个值升序或降序。相邻交换验证。把相邻两个对象拎出来前面累计量记为 S分别写两种顺序下的代价表达式化简出排序条件。排序后扫描。按推导出的关键字排序再线性扫一遍计算真正的答案。怎么快速判断一道题是不是推公式题特征非常明显给一堆二元组或多元组让你排列后求最大值最小、总和最小、某种极值而且 n 的范围大到你根本不可能枚举全排列。只要满足这个特征优先考虑相邻交换论证。5.2 五个高频翻车点竞赛里推公式题错的原因高度集中我整理了一个速查表。错误类型现象解决方法前缀乘积溢出C/Java 答案变成负数用 long long / BigInteger / Python答案初始化为 0风险全为负数时输出 0求最大值初始化为负无穷国王等固定元素参与排序整体顺序全错固定元素排除在排序外但参与前缀计算用浮点数比较分数精度误差导致排序错用交叉相乘不用除法扫描时忘记累加前缀后面的值全错先更新答案再累加当前元素其中“用浮点比较”是个隐蔽问题。比如排序条件本质是比较 a/b 和 c/d 时不要写成 a / b c / d因为浮点数可能丢精度要写成 a * d c * b。整数运算永远是最安全的。5.3 和蓝桥杯真题怎么对应蓝桥杯的题面虽然不像 ACM 那么复杂但省赛里出现过大量“排序后求最值”的贪心题比如活动安排、最小延迟任务调度、区间覆盖本质上都是先证明一个局部规则再排序。刷历年真题时看到题面里有“安排顺序”“排队”“调度”“叠放”这些字眼就可以优先往相邻交换的方向想。另外想单独提一下删数问题。它和推公式里的排序型贪心不完全一样它依靠的是“每一步删除一个局部逆序数字”的迭代思想属于局部贪心推进的模型同样需要证明每次决策不会让答案变差。考场上把这些模型分清楚比死记模板重要得多。还有归并排序、KMP 这类经典算法是独立专题推公式题主要服务的是贪心策略部分别混在一起刷。最后说点实在的我个人在实际训练里最大的体会是推公式题考的从来不是“会不会排序”而是“能不能在几分钟内完成一次相邻交换的推导”。蓝桥杯赛场上压力很大很多人第一反应是回忆看题解时记住的结论题目一变就懵。我的建议是平时练真题时每道排序型贪心题都在草稿纸上把两个相邻元素拎出来写一遍哪怕只是粗糙地推一下。坚持二十道题之后你会形成一种条件反射看到“最大化最小值”“最小值最大”这类关键词就知道该去找相邻交换的不等式了。最后再分享一个小习惯推完公式之后用极端数据自测一下。比如把所有 w 设成 1、所有 s 设成 1或者把所有 a 设成 1、所有 b 设成 1看排序结果和最终答案是否符合直觉。这种自测成本很低却往往能拦住大部分因为排序规则写反、初始化错误导致的低级失误。推公式这件事练的是手上的推导功夫和脑中的条件反射多写几次考场上的“灵光一现”其实都是平时演算的积累。