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

1. 问题背景与核心思路国王游戏是NOIP2012提高组的经典题目题目描述看似简单却暗藏玄机。想象这样一个场景国王带着n位大臣玩金币奖励游戏每位大臣左右手各写一个数字。奖励规则是每位大臣获得的金币数等于前面所有人左手数字乘积除以自己右手数字的整数部分。我们的任务是重新排列大臣顺序使得获得最多金币的大臣所得尽可能少。我第一次看到这个问题时直觉告诉我应该用贪心算法。但具体怎么贪直接按左手数字从小到大排或者按右手数字从大到小排实测发现这些简单策略都会出错。后来通过数学推导发现正确的排序依据应该是大臣左右手数字的乘积。这个结论看似简单但背后的数学证明却非常精妙。2. 贪心策略的数学证明2.1 相邻交换法的关键思路要证明按左右手乘积排序的正确性最有力的工具就是相邻交换法。假设当前有相邻的两位大臣A和BA在B前面。设他们前面所有人的左手乘积为P我们来比较两种排列方式当A在前时A获得金币P / A.rightB获得金币(P × A.left) / B.right当B在前时B获得金币P / B.rightA获得金币(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并除以PP0得到 A.left × A.right ≤ B.left × B.right这意味着只要A的左右手乘积小于等于B的就应该让A排在前面。这个简洁的数学结论完美解决了排序依据问题。注意这个证明过程中我们忽略了P0的情况但根据题意a,b0P永远不会为0。3. 高精度处理的必要性3.1 数据范围的陷阱题目中n≤1000a,b10000最坏情况下所有左手数字都是9999乘积将达到9999^1000≈10^4000远超long long的范围约10^18。这就是为什么必须使用高精度运算。我在第一次实现时就踩了这个坑用普通整型写了贪心排序后样例能过但提交后大量WA。后来仔细看数据范围才恍然大悟这就是算法竞赛中常见的数据范围陷阱。3.2 高精度实现要点我们需要实现三个核心操作高精度乘法大数×小数高精度除法大数÷小数高精度比较找出最大值以乘法为例关键代码实现如下vectorint multiply(vectorint a, int b) { vectorint res; int carry 0; for(int i0; ia.size(); i) { carry a[i] * b; res.push_back(carry % 10); carry / 10; } while(carry) { res.push_back(carry % 10); carry / 10; } return res; }除法操作稍复杂需要注意从高位到低位处理vectorint divide(vectorint a, int b) { vectorint res; int remainder 0; for(int ia.size()-1; i0; 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; vectorint product; // 前面所有人的左手乘积 vectorint reward; // 获得的金币数 };4.2 排序与计算流程主算法流程分为三步按左右手乘积排序遍历计算每位大臣的金币找出最大值关键实现片段bool cmp(Minister a, Minister b) { return a.left*a.right b.left*b.right; } int main() { // 输入数据 sort(ministers1, ministersn1, cmp); vectorint total(1, king.left); // 初始为国王左手数 vectorint max_reward; for(int i1; in; 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 性能优化实践在实际编码中发现几个优化点乘积可以递推计算不需要每次都从头乘高精度数用vector存储时低位在前更方便运算比较函数先比位数再逐位比较一个容易忽略的边界情况是当所有大臣获得金币都为0时要确保输出0而不是空值。5. 常见错误与调试方法5.1 典型错误案例贪心策略错误按单一维度排序高精度溢出没考虑最大乘积位数除法错误余数处理不当导致结果错误比较函数错误没正确处理前导零5.2 调试技巧分享我推荐使用这个小数据测试2 1 1 1 2 1 3正确输出应为0可以检测除法边界情况。另一个有用的测试是3 1 1 2 3 7 4 4 6正确输出为2验证贪心策略。5.3 高精度实现的替代方案如果时间紧张可以考虑使用Java的BigInteger类使用Python原生大整数支持预先生成高精度模板但在算法竞赛中掌握手写高精度仍是必备技能。建议平时就准备好高精度模板包括加减乘除和比较操作。