BISHI53　[P1080] 国王游戏(简化版)¶

中等通过率 64.15%python3样例通过牛客 AC

牛客原题　源码

讲解章节：贪心

一句话

排大臣顺序，最小化「拿金币最多的人」。

解题思路¶

这题考什么¶

相邻交换（exchange argument）推排序规则的经典模板题。设某两位相邻大臣为 i、j，他们前面所有人（含国王）的左手乘积为 S，

i 在前：两人分别拿 floor(S/b_i)、floor(S*a_i/b_j)
j 在前：两人分别拿 floor(S/b_j)、floor(S*a_j/b_i)

去掉下取整比较（S 是公共因子，量级足够大时不改变大小关系），两种排法的最大值分别由 Sa_i/b_j 与 Sa_j/b_i 主导，即比较 a_ib_i 与 a_jb_j —— 按 a_i * b_i 升序排，前面的人吃亏更小。

排好之后从前往后累乘 a，逐个算 floor(前缀乘积 / b_i) 取最大值即可。

数据规模与复杂度¶

n <= 60，a_i,b_i <= 8。排序 O(n log n)，累乘 O(n)。真正的难点是 ∏a 最大到 8^60 ≈ 1.8e54，C++ 必须写高精度； Python 的 int 天生任意精度，这题因此变成纯模板。

坑在哪¶

国王固定在最前，他自己不参与排序、也不领金币，但 a_0 要计入前缀乘积， b_0 完全没用（读掉丢弃即可）；
是「乘积除以 b_i 下取整」，必须用整除 //，用浮点会炸精度；
前缀乘积是「不含自己」的：先算 floor(prefix / b_i)，再把 a_i 乘进去。顺序颠倒会把自己的 a_i 也算进分子，结果偏大；
排序键是乘积 a_i*b_i，不是 a_i 或 b_i 单独一个，也不是 a_i/b_i。

样例复核¶

国王 (1,1)，大臣 (2,3)、(7,4)、(4,6)，乘积键分别是 6、28、24，升序排成 (2,3) -> (4,6) -> (7,4)。前缀从 a_0 = 1 开始： (2,3)：1 // 3 = 0，前缀变 12 = 2； (4,6)：2 // 6 = 0，前缀变 24 = 8； (7,4)：8 // 4 = 2，前缀变 8*7 = 56。最大值 2，与样例一致 ✓。

Python 的任意精度整数见 22-高精度与大整数，相邻交换法见 47-贪心。

参考实现¶

solutions/BISHI53.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a0 = int(data[1])                 # data[2] 是 b0，用不到
    pairs = []
    for i in range(n):
        # 国王占了 data[1]、data[2]，所以第 i 位大臣从下标 3+2i 开始
        a = int(data[3 + 2 * i])
        b = int(data[4 + 2 * i])
        pairs.append((a * b, a, b))   # 把排序键放在元组首位，直接用默认排序
    pairs.sort()                      # 按 a*b 升序

    prefix = a0                       # 当前大臣前面所有人的左手乘积
    ans = 0
    for _, a, b in pairs:
        v = prefix // b               # 整除，浮点在 8^60 量级会彻底失真
        if v > ans:                   # 只关心「拿得最多的那个人」
            ans = v
        prefix *= a                   # 算完自己再把 a_i 并入前缀，供后面的人用
    sys.stdout.write(str(ans) + "\n")


main()

BISHI53 [P1080] 国王游戏(简化版)¶