P1080国王游戏题解：贪心排序证明与4000位高精度实现

做竞赛训练这些年P1080 国王游戏是我几乎每年都会拿出来让新人受虐一遍的题。它看着人畜无害国王和大臣排排队每个大臣拿个金币好像算一算就能答案。可真上手就会发现排序规则要证明高精度要手写数据范围还卡得死死的。这篇文章我把这道题的完整思路、贪心证明、高精度实现以及我踩过的坑全部拆开希望后来的人少走弯路。这道题适合正在刷贪心和基础数论的选手也适合刚学完高精度、想找综合题练手的人。它不像某些难题那样需要很高深的算法知识但非常考验基本功和对排序依据的理解。1. 题面拆解所有大臣的奖赏到底是怎么算出来的1.1 把故事翻译成数学运算先把题意用我自己习惯的方式复述一遍。国王站队首后面跟着 n 个大臣。每个人左右手各写一个正整数国王也写了一个正整数。站在某个位置的大臣他的奖赏是这样算的把他排在他之前的所有人包括国王和排在他前面的大臣的左手上数字全部乘起来得到乘积 T然后除以他自己的右手数字向下取整。用公式表达就是奖赏 floor(T / b[i])。注意这个 T 里不包含他自己的左手数字只包含前面所有人的左手数字。国王本人是不领奖赏的但国王的左手数字会参与后面每个大臣的 T 计算。目标也很直白通过调整这 n 个大臣的先后顺序让所有大臣中奖赏最大的那个人的奖赏尽可能小。最后输出这个最小的最大值。这个描述看起来就是一个排序优化问题但难点在于到底按什么排序很多人第一反应是模拟枚举全排列但 n 最大可以到 1000全排列连边都摸不到。这题真正要做的是先找出一个确定的排序规则再顺着这个规则把答案算出来。1.2 最容易犯的错把题当成纯排序模拟我第一次做的时候也中招了想着那就随便按某个关键字排个序然后从左到右算一遍不就完了。但问题在于按 a 排、按 b 排、按 a/b 排结果都不一样。常见的错误思路有这么几种按左手数字 a 升序排。理由是左手小的人放前面后面人拿到的 T 就小。听起来有道理但完全忽略了右手 b 的影响。如果一个人左手很小但右手也小让他排前面他自己拿到的奖赏反而可能特别大。按右手数字 b 降序排。理由是右手大的人除出来的商小放前面不吃亏。可是右手大的人左手也可能很大把他放前面会让后面所有人 T 变大整体收益未必好。按 a/b 或者 b/a 排。这是很多人的下一步尝试但仍然不对因为题目里的奖赏不是简单的加减而是先累积乘积再除法前一项对后面的影响是非线性的。这些直觉之所以不管用是因为我们没有把最大值最小化这个问题进行严格的数学处理。只能说靠猜排序很容易翻车。1.3 数据范围决定了一件事必须用高精度这题 n 最多 1000每个 a、b 最大都是 10000。就算所有 a 都取 1乘积也有 10^4000 这个量级如果 a 取满 10000那乘积位数能到 4000 甚至 4001 位。long long 最大才 19 位差距大到离谱。所以不管排序规则最后是什么在算答案这一步都必须上高精度。这也是为什么我说这道题是两座山先翻过贪心排序这座山再翻过高精度实现这座山。哪个翻不过去都拿不了全分。2. 贪心排序为什么是a×b相邻交换法的完整证明2.1 三种排序直觉的博弈我们先用直觉筛一遍。只看左手 a 的问题在于一个人对后面的影响是乘法累乘越到后面越爆炸只看右手 b 的问题在于右手只影响他本人这一次计算却无法控制他对全局乘积的贡献。那是不是把 a 和 b 综合起来看有个很经典的操作叫相邻交换法。思路是我不看全局只盯着相邻的两个人。如果相邻两人的顺序是不优的那我交换他们整个方案不会变差。如果任何相邻逆序都可以通过交换修正那么消除所有逆序之后得到的排列就是最优的。排序依据自然就出来了。按照这个思路我们假设有相邻的两个人 i 和 j现在 i 排在 j 前面。设在他们之前的所有人左手乘积为 S不包含 i、j 自己的左手。接下来只比较交换前后这两个人的奖赏因为交换相邻两人不会影响他们之前的人和之后的人——之前的人不受影响之后的人的 T 是 S × a_i × a_j 乘以后面的人跟 i、j 谁在前无关。2.2 相邻交换法的推导过程交换前i 的奖赏是S / b_i向下取整下面证明用实数比较取整不影响结论j 的奖赏是S × a_i / b_j。交换后j 的奖赏是S / b_ji 的奖赏是S × a_j / b_i。我们希望交换后的最大值不超过交换前的最大值也就是说排序完成后最大值不会因为交换而变大。需要证明max( S/b_i, S×a_i/b_j ) max( S/b_j, S×a_j/b_i )假设我们让两个人按a_i × b_i a_j × b_j的顺序排列也就是乘积小的在前。两边同时乘以S / (b_i × b_j)因为 S、b_i、b_j 都是正数不等号方向不变得到S × a_i / b_j S × a_j / b_i这个式子的意思是交换前 j 的奖赏S×a_i/b_j不超过交换后 i 的奖赏S×a_j/b_i。也就是说交换后涉及到的那个较大的项在交换前已经存在一个不小于它的值。再看交换前的最大值里还有一个S/b_i。因为 a_i 1所以S × a_i / b_j S / b_j而S / b_j正是交换后 j 的奖赏。所以交换前的最大值至少不小于交换后的两个值里较小的那个。综合起来两个关键不等式都成立于是交换前 max 一定不小于交换后 max。这意味着只要相邻两人的a_i × b_i a_j × b_j把他们交换一下整个队列的最大奖赏不会变差。不断执行这样的交换最终所有人会按a × b升序排列最大值达到最小。如果两个人的a × b相等无论谁在前上面的推导都退化为等号所以顺序没有影响。2.3 证明里容易被忽略的边界条件很多人会卡在为什么S × a_i / b_j S / b_j这一步其实关键就是a_i 1。如果某个大臣左手数字是 0这个不等式就可能不成立整个贪心也就塌了。所以题目必须保证所有数字是正整数这也是为什么原题不给 0 的原因。还有一个隐含条件S 必须是正数。如果 S 为 0奖赏全是 0比较就没意义了。好在此题所有左手数字都是正整数S 只会越乘越大。从考场实战角度说这个相邻交换法不仅适用于这道题它几乎是我的默认武器。凡是碰到通过排列让某个极值最小/最大的题我都会先挑两个相邻元素写一写交换前后的表达式看看能不能推出一个比较规则。如果能推出单调的比较依据排序就稳了。3. 高精度实现让乘积老老实实算到4000位也不溢出3.1 先估算规模再决定怎么写高精度的实现方式和数据范围强相关。这题里 a、b 最大 10000最多 1000 个数相乘位数最多到 4000 出头。这里推荐用十进制压位也就是用一个 int 存 4 位十进制数vector 长度只需要 1000 左右计算量非常小。为什么压 4 位而不是压 9 位因为9999 × 10000 进位大概是 10^8int 能轻松装下如果压 9 位乘法时就可能溢出 long long 的边界处理起来反而麻烦。压 4 位是 C 手写高精度最舒服的平衡点。3.2 存储约定低位在前输出倒序我习惯用vectorint存大数下标 0 存个位下标 1 存万位。好处是乘法进位可以顺着下标走符合直觉。定义一个大数类型using BigInt vectorint;初始化一个数比如国王左手数字BigInt num; int x p[0].a; while (x) { num.push_back(x % 10000); x / 10000; }这样num[0]是个位num.back()是最高位。手写乘法、除法、比较都会围绕这个约定展开。3.3 大数乘法逐位乘进位单独处理乘法的操作对象是大数 × 普通整数。因为 a[i] 最大 10000所以乘数不会超过 10000处理起来非常简单BigInt multiply(const BigInt x, int y) { BigInt res(x.size()); int carry 0; for (int i 0; i (int)x.size(); i) { long long cur (long long)x[i] * y carry; res[i] cur % 10000; carry cur / 10000; } while (carry) { res.push_back(carry % 10000); carry / 10000; } return res; }注意进位可能不止一次比如9999 × 10000 99990000carry 就接近 10000所以要用while (carry)循环把 carry 拆成多位压进数组而不是只用 if。3.4 大数除法从高位往低位做竖式除法是大数 ÷ 普通整数这里不能用乘法那种正着遍历的方式必须倒着模拟手算竖式BigInt divide(const BigInt x, int y) { BigInt res(x.size(), 0); int rest 0; for (int i (int)x.size() - 1; i 0; i--) { long long cur (long long)rest * 10000 x[i]; res[i] cur / y; rest cur % y; } while (res.size() 1 res.back() 0) { res.pop_back(); } return res; }除法之后一定记得把高位的 0 去掉。比如一个大数除以一个很大的 b商可能比原来的数短很多不去前导 0 会导致后面比较大小出错。3.5 完整代码与注释下面是完整的 C 解法。这里排序用 lambda按乘积升序国王单独放在数组下标 0 的位置不参与排序队首乘积初始化为国王左手数字然后逐个计算每个大臣的奖赏同时更新乘积。#include bits/stdc.h using namespace std; struct Person { int a, b; } p[1005]; using BigInt vectorint; BigInt multiply(const BigInt x, int y) { BigInt res(x.size()); int carry 0; for (int i 0; i (int)x.size(); i) { long long cur (long long)x[i] * y carry; res[i] cur % 10000; carry cur / 10000; } while (carry) { res.push_back(carry % 10000); carry / 10000; } return res; } BigInt divide(const BigInt x, int y) { BigInt res(x.size(), 0); int rest 0; for (int i (int)x.size() - 1; i 0; i--) { long long cur (long long)rest * 10000 x[i]; res[i] cur / y; rest cur % y; } while (res.size() 1 res.back() 0) { res.pop_back(); } return res; } bool bigger(const BigInt x, const BigInt y) { if (x.size() ! y.size()) return x.size() y.size(); for (int i (int)x.size() - 1; i 0; i--) { if (x[i] ! y[i]) return x[i] y[i]; } return false; } void output(const BigInt x) { printf(%d, x.back()); for (int i (int)x.size() - 2; i 0; i--) { printf(%04d, x[i]); } printf(\n); } int main() { int n; scanf(%d, n); for (int i 0; i n; i) { scanf(%d%d, p[i].a, p[i].b); } sort(p 1, p n 1, [](const Person u, const Person v) { return (long long)u.a * u.b (long long)v.a * v.b; }); BigInt acc; int t p[0].a; while (t) { acc.push_back(t % 10000); t / 10000; } BigInt best(1, 0); for (int i 1; i n; i) { BigInt cur divide(acc, p[i].b); if (bigger(cur, best)) best cur; acc multiply(acc, p[i].a); } output(best); return 0; }注意输出函数里printf(%04d)是关键。因为万进制存的是 4 位一组中间某些组可能是 3 位、2 位甚至 1 位不补 0 输出的数字就是错的。最高位不用补 0直接打印就行。4. 提交过程中我踩过的三个坑比较函数、初始化和读入顺序4.1 排序比较器里别用除法老老实实写乘法有一种看起来很省事的写法是return (double)u.a / u.b (double)v.a / v.b。但浮点数在边界处会有精度问题而且这题的比较依据是 a×b不是 a/b。就算你意识到了比较依据想用a / b来近似达到某种效果那也是错的。正确写法只有一种在比较器里直接计算两个乘积用 long long 装起来再比较。10000 × 10000 10^8int 其实也放得下但写成 long long 更稳妥也更容易让读代码的人明白你的意图。4.2 国王的位置处理左手参与计算右手不参与排序读入的顺序是国王、大臣、大臣……很多人做的时候把所有人都塞进一个数组然后整体排序。这个错很隐蔽因为小数据可能恰好跑不出差异但一旦国王的 a×b 比较小排序后大臣跑到国王前面T 的计算就全乱了。正确做法是国王固定在第一个排序区间只包括大臣。国王的左手数字只用来初始化 acc国王的右手数字没有任何用处不需要参与任何计算。我一开始就是因为把国王也排进去了导致样例都过不了后来单步调试才意识到的。这里也说明了一个通用经验涉及队首固定的排序题最好把队首单独存放在数组下标 0 的位置排序从下标 1 开始。代码可读性也会好很多。4.3 答案初始化别让 0 变成比所有奖赏都小best 变量用来记录所有大臣奖赏的最大值初始化为 0 是安全的因为奖赏都是非负整数。但如果你为了省代码把 best 初始化为空 vector又用bigger(cur, best)去比较空的 vector 长度为 0任何非空 cur 都会被判为更大所以不会出错。真正要小心的是没有大臣的情况。虽然原题 n≥1但如果是自己造数据或者扩展版本n 可以为 0这时候 acc 只有国王左手循环一次都不执行直接输出 best 就会输出一个空数。我建议无论如何都把 best 初始化为包含一个 0 的 vector输出函数也能正常打印 0这样代码更健壮。4.4 高精度除法里的前导零和余数细节做除法的时候res(i)的初始大小和 x 一样但商的高位经常会变成 0。例如 acc 是 4000 位除以 10000商只有 3996 位左右。如果不把高位 0 弹掉后面比较大小的时候长度判断就会出错。除法的余数 rest 也值得注意。rest 最大是 9999乘以 10000 再加上当前位 9999接近 10^8int 是够放的但我还是习惯用 long long 存 cur避免以后改动压位位数时踩坑。另外如果 b 正好能整除rest 会变成 0这不影响循环只要最后正确弹出前导 0 即可。一个我调试了很久的小坑是乘法里的进位循环如果把while (carry)写成if (carry)当原数高位已经是 0 且进位还有多位时高位的进位会丢失。看似只是少了几位实际答案会差好几个数量级。这种错误最快的方式就是拿一组随机大数对拍一秒钟就能暴露。5. 从国王游戏中学到的通用算法素养贪心证明、对拍验证和考场心态5.1 相邻交换法的适用边界相邻交换法不是万能的但适用范围相当广。它成立的标志是你交换两个相邻元素只影响这两个元素参与计算的目标值不影响其他元素。典型的例子有调度问题、排队打水的一些变种、部分区间排序题。判断能否使用的办法很简单列出交换前后两个元素的表达式看能不能推出一个只和自身参数有关的比较规则。如果推导过程中出现了第三者参数那相邻交换法可能就不适用这时候要考虑别的方法比如二分答案贪心验证。国王游戏正好是最标准的相邻交换法每个人只需要自己的 a、b 以及前面乘积 S而 S 跟两个人内部顺序无关。5.2 考场上不确定排序时写个暴力对拍如果你的证明能力还没那么强有一个非常实用的替代方案先写一个暴力枚举全排列的程序取 n 小到 5 或 6 时跑出正确答案再写排序贪心程序随机生成数据对拍。如果几百组数据全部一致基本可以确信排序规则是对的。这个方法看起来笨但极其有效。我在训练和真实比赛中都靠它救过命。关键是生成随机数据时要覆盖极端值某些 a 为 1某些 b 为 10000某些 a 和 b 都很大。只有把边界覆盖住对拍才有意义。5.3 考场上的时间分配先想排序再写高精度这类题目最容易犯的战术错误是一上来就写高精度模板写完了才发现排序是错的白费大量时间。我的建议是反着来先用 10 到 20 分钟想清楚排序依据并证明或者用暴力对拍验证。确认排序规则后再花 20 到 30 分钟写高精度和主流程。高精度代码是体力活不太会给你带来灵感所以放在思路确认之后写最稳妥。另外如果考场时间紧张可以先写不带高精度的版本只取模或者仅用 long long 跑小数据拿部分分再用高精度补全。NOIP 这类竞赛是按数据点给分的能拿的部分分一定要先拿到手。最后说点个人体会。国王游戏这道题我第一次做的时候卡在排序上整整两天最后看到题解里按 a×b 排序这个结论时还有点不服气直到自己把相邻交换法完整推导了一遍才真正接受。从那以后我再也不靠感觉去猜贪心规则了任何排序依据都先写表达式验证。高精度部分也多亏这道题的毒打让我把压位、前导零、进位这些细节彻底练熟了。如果你能把这道题完全吃透后面再遇到类似的贪心加高精度组合题就会有底气很多。