国王游戏题解

问题分析

题目要求重新排列大臣的顺序，使得获得最多金币的大臣所获金币尽可能少。每位大臣获得的金币计算公式为：

$$\text{金币数} = \left\lfloor \frac{\text{前面所有人左手数的乘积}}{\text{自己右手上的数}} \right\rfloor $$

关键思路

贪心策略

通过数学推导可以证明，最优的排列顺序是按照 $a_i \times b_i$ 的大小进行排序，其中 $a_i$ 是左手数字，$b_i$ 是右手数字。

证明思路

考虑相邻两个大臣 $i$ 和 $i+1$ 交换位置的影响：

• 交换前：大臣 $i$ 获得 $\frac{S}{b_i}$，大臣 $i+1$ 获得 $\frac{S \times a_i}{b_{i+1}}$
• 交换后：大臣 $i+1$ 获得 $\frac{S}{b_{i+1}}$，大臣 $i$ 获得 $\frac{S \times a_{i+1}}{b_i}$

其中 $S$ 是前面所有大臣左手数的乘积。要使交换后最大值不增加，需要满足：

$$\max\left(\frac{S}{b_{i+1}}, \frac{S \times a_{i+1}}{b_i}\right) \leq \max\left(\frac{S}{b_i}, \frac{S \times a_i}{b_{i+1}}\right) $$

化简后得到：$a_i \times b_i \leq a_{i+1} \times b_{i+1}$

算法步骤

1. 输入数据：读取国王和大臣的左右手数字
2. 排序：按照 $a_i \times b_i$ 从小到大对大臣排序
3. 计算最大金币：
   • 维护前缀乘积（使用高精度）
   • 对于每个大臣，计算 前缀乘积 / 右手数字
   • 记录最大值

代码核心组件

高精度类 bigint

• 支持大数的存储和运算
• 实现乘法、除法、比较等操作
• 使用 vector 存储数字，每位存储一个十进制数字

关键函数

• operator*：高精度乘法
• operator/：高精度除以整数
• operator<：高精度比较

复杂度分析

• 时间复杂度：$O(n \log n + n \times L^2)$，其中 $L$ 是数字位数
• 空间复杂度：$O(n \times L)$

样例分析

对于样例：

3
1 1
2 3
7 4
4 6

计算每个大臣的 $a_i \times b_i$：

• 大臣1：$2 \times 3 = 6$
• 大臣2：$7 \times 4 = 28$
• 大臣3：$4 \times 6 = 24$

排序结果：

按 $a_i \times b_i$ 从小到大排序：大臣1(6) < 大臣3(24) < 大臣2(28)

计算过程：

1. 前缀乘积 = 1（国王左手）
2. 大臣1：金币 = 1/3 = 0
3. 前缀乘积 = 1×2 = 2
4. 大臣3：金币 = 2/6 = 0
5. 前缀乘积 = 2×4 = 8
6. 大臣2：金币 = 8/4 = 2

最大金币数为 2