[NOIP2012 提高组] 国王游戏：贪心策略的数学证明与高精度实现详解

1. 问题背景与核心思路

国王游戏是NOIP2012提高组的经典题目，题目描述看似简单却暗藏玄机。想象这样一个场景：国王带着n位大臣玩金币奖励游戏，每位大臣左右手各写一个数字。奖励规则是：每位大臣获得的金币数等于前面所有人左手数字乘积除以自己右手数字的整数部分。我们的任务是重新排列大臣顺序，使得获得最多金币的大臣所得尽可能少。

我第一次看到这个问题时，直觉告诉我应该用贪心算法。但具体怎么贪？直接按左手数字从小到大排？或者按右手数字从大到小排？实测发现这些简单策略都会出错。后来通过数学推导发现，正确的排序依据应该是大臣左右手数字的乘积。这个结论看似简单，但背后的数学证明却非常精妙。

2. 贪心策略的数学证明

2.1 相邻交换法的关键思路

要证明按左右手乘积排序的正确性，最有力的工具就是相邻交换法。假设当前有相邻的两位大臣A和B，A在B前面。设他们前面所有人的左手乘积为P，我们来比较两种排列方式：

当A在前时：

• A获得金币：P / A.right
• B获得金币：(P × A.left) / B.right

当B在前时：

• B获得金币：P / B.right
• A获得金币：(P × B.left) / A.right

我们需要保证A在前时的最大值更小，即： max(P/A.right, (P×A.left)/B.right) ≤ max(P/B.right, (P×B.left)/A.right)

2.2 不等式化简过程

通过分析可以发现，P/A.right和P/B.right都不会成为最大值（因为后面项的分子更大）。因此只需比较： (P×A.left)/B.right ≤ (P×B.left)/A.right

两边同时乘以A.right×B.right并除以P（P>0）得到： A.left × A.right ≤ B.left × B.right

这意味着只要A的左右手乘积小于等于B的，就应该让A排在前面。这个简洁的数学结论完美解决了排序依据问题。

注意：这个证明过程中我们忽略了P=0的情况，但根据题意a,b>0，P永远不会为0。

3. 高精度处理的必要性

3.1 数据范围的陷阱

题目中n≤1000，a,b<10000，最坏情况下所有左手数字都是9999，乘积将达到9999^1000≈10^4000，远超long long的范围（约10^18）。这就是为什么必须使用高精度运算。

我在第一次实现时就踩了这个坑，用普通整型写了贪心排序后，样例能过但提交后大量WA。后来仔细看数据范围才恍然大悟，这就是算法竞赛中常见的"数据范围陷阱"。

3.2 高精度实现要点

我们需要实现三个核心操作：

1. 高精度乘法（大数×小数）
2. 高精度除法（大数÷小数）
3. 高精度比较（找出最大值）

以乘法为例，关键代码实现如下：

vector<int> multiply(vector<int> &a, int b) { vector<int> res; int carry = 0; for(int i=0; i<a.size(); i++) { carry += a[i] * b; res.push_back(carry % 10); carry /= 10; } while(carry) { res.push_back(carry % 10); carry /= 10; } return res; }

除法操作稍复杂，需要注意从高位到低位处理：

vector<int> divide(vector<int> &a, int b) { vector<int> res; int remainder = 0; for(int i=a.size()-1; i>=0; i--) { remainder = 10 * remainder + a[i]; res.push_back(remainder / b); remainder %= b; } reverse(res.begin(), res.end()); while(res.size()>1 && res.back()==0) res.pop_back(); return res; }

4. 完整实现与优化技巧

4.1 结构体设计

将每个大臣的信息封装成结构体更清晰：

struct Minister { int left, right; vector<int> product; // 前面所有人的左手乘积 vector<int> reward; // 获得的金币数 };

4.2 排序与计算流程

主算法流程分为三步：

1. 按左右手乘积排序
2. 遍历计算每位大臣的金币
3. 找出最大值

关键实现片段：

bool cmp(Minister a, Minister b) { return a.left*a.right < b.left*b.right; } int main() { // 输入数据 sort(ministers+1, ministers+n+1, cmp); vector<int> total(1, king.left); // 初始为国王左手数 vector<int> max_reward; for(int i=1; i<=n; i++) { ministers[i].reward = divide(total, ministers[i].right); total = multiply(total, ministers[i].left); if(compare(ministers[i].reward, max_reward) > 0) { max_reward = ministers[i].reward; } } // 输出max_reward }

4.3 性能优化实践

在实际编码中发现几个优化点：

1. 乘积可以递推计算，不需要每次都从头乘
2. 高精度数用vector存储时，低位在前更方便运算
3. 比较函数先比位数再逐位比较

一个容易忽略的边界情况是：当所有大臣获得金币都为0时，要确保输出0而不是空值。

5. 常见错误与调试方法

5.1 典型错误案例

1. 贪心策略错误：按单一维度排序
2. 高精度溢出：没考虑最大乘积位数
3. 除法错误：余数处理不当导致结果错误
4. 比较函数错误：没正确处理前导零

5.2 调试技巧分享

我推荐使用这个小数据测试：

2 1 1 1 2 1 3

正确输出应为0，可以检测除法边界情况。

另一个有用的测试是：

3 1 1 2 3 7 4 4 6

正确输出为2，验证贪心策略。

5.3 高精度实现的替代方案

如果时间紧张，可以考虑：

1. 使用Java的BigInteger类
2. 使用Python原生大整数支持
3. 预先生成高精度模板

但在算法竞赛中，掌握手写高精度仍是必备技能。建议平时就准备好高精度模板，包括加减乘除和比较操作。