题目分析

我们需要安排 n 个大臣的顺序，使得获得最多金币的大臣所获得的金币数尽可能少。

金币计算公式

对于第 i 个大臣，其金币数为：

\text{coins}_i = \left\lfloor \frac{\prod_{j=0}^{i-1} a_j}{b_i} \right\rfloor

其中 a_0,b_0 表示国王的左右手数字。

贪心策略证明

我们需要找到一种排序方式，使得所有大臣中金币数的最大值最小化。

按 a_i \cdot b_i升序排列是最优策略。

数学证明

考虑相邻两个大臣 i 和 j，且 a_i \cdot b_i > a_j \cdot b_j，设\text{S} = \prod_{k=0}^{i-1} a_k

交换前（顺序：i→j）:

  • 大臣 i 的金币：\frac{S}{b_i}
  • 大臣 j 的金币：\frac{S \cdot a_i}{b_j}

交换后（顺序：j→i）:

  • 大臣 j 的金币：\frac{S}{b_j}
  • 大臣 i 的金币：\frac{S \cdot a_j}{b_i}

由于 a_i \cdot b_i > a_j \cdot b_j，可得：

\frac{a_i}{b_j} > \frac{a_j}{b_i} \implies \frac{S \cdot a_i}{b_j} > \frac{S \cdot a_j}{b_i}

因此交换前的最大金币数为 \frac{S \cdot a_i}{b_j}，交换后的最大金币数为 \max\left(\frac{S}{b_j}, \frac{S \times a_j}{b_i}\right)，且：

\max\left(\frac{S}{b_j}, \frac{S \cdot a_j}{b_i}\right) < \frac{S \cdot a_i}{b_j}

所以交换后最大值不会更大，按 a_i \cdot b_i 升序排列是最优策略。

代码实现

import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    a0, b0 = map(int, input().split())
    arr = [tuple(map(int, input().split())) for _ in range(n)]
    
    # 按a_i*b_i升序排列
    arr.sort(key=lambda x: x[0]*x[1])
    
    max_coins = 0
    prefix = a0   # 记录前缀乘积
    
	# 找出金币最多的大臣的金币数
    for a, b in arr:
        coins = prefix // b
        if coins > max_coins:
            max_coins = coins
        prefix *= a
    
    print(max_coins)

if __name__ == "__main__":
    main()
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(n)