国王游戏

形式化题目

给定正整数 $n$ ，以及国王的左右手数值对 $(a_0, b_0)$ ，和 $n$ 位大臣的数值对 $(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$ 。

国王始终排在队伍首位（位置 $0$ ）。若将 $n$ 位大臣排成一个队伍序列 $p_1, p_2, \dots, p_n$ ，则第 $i$ 位大臣（位置 $i$ ）获得的金币数为：

w_i = \left\lfloor \frac{a_0 \prod_{j=1}^{i-1} a_{p_j}}{b_{p_i}} \right\rfloor

请确定大臣的一个排列 $p$ ，使得获得奖赏最多的大臣所获奖赏尽可能小，即求出：

\min_{p} \max_{1 \le i \le n} w_i

正解

思路

本题要求在所有可能的大臣排列中最小化获得金币的最大值，是一个典型的排列决策问题。我们可以使用**邻项交换法（Exchange Argument）**推导出最优的排队准则。

1. 邻项交换法推导

假设当前排列中，有两个相邻的大臣排在第 $i$ 位和第 $i+1$ 位。

记排在他们前面的所有人（包括国王）左手上的数的乘积为 $P$ 。交换他们两人的位置，不会影响排在第 $i$ 位之前的大臣，也不会改变排在第 $i+1$ 位之后大臣前面的左手乘积（因为 $P \cdot a_i \cdot a_{i+1} = P \cdot a_{i+1} \cdot a_i$ ）。

因此，交换只可能改变这两位大臣自身的金币数。

交换前（大臣 $i$ 在前，大臣 $i+1$ 在后）：
- 大臣 $i$ 的金币： $w_i = \left\lfloor \frac{P}{b_i} \right\rfloor$
- 大臣 $i+1$ 的金币： $w_{i+1} = \left\lfloor \frac{P \cdot a_i}{b_{i+1}} \right\rfloor$
- 这两人中的最大金币为：
  $M_1 = \max\left(\left\lfloor \frac{P}{b_i} \right\rfloor, \left\lfloor \frac{P \cdot a_i}{b_{i+1}} \right\rfloor\right)$
交换后（大臣 $i+1$ 在前，大臣 $i$ 在后）：
- 大臣 $i+1$ 的金币： $w'_{i+1} = \left\lfloor \frac{P}{b_{i+1}} \right\rfloor$
- 大臣 $i$ 的金币： $w'_i = \left\lfloor \frac{P \cdot a_{i+1}}{b_i} \right\rfloor$
- 这两人中的最大金币为：
  $M_2 = \max\left(\left\lfloor \frac{P}{b_{i+1}} \right\rfloor, \left\lfloor \frac{P \cdot a_{i+1}}{b_i} \right\rfloor\right)$

2. 比较两状态的最大值

为了让整体最大值不增加，我们需要寻找使 $M_1 \le M_2$ 的条件。

将四项均乘以 $\frac{b_i b_{i+1}}{P}$ （在实数范围上比较关键项大小）：

交换前的两项等价于： $b_{i+1}$ 与 $a_i b_i$
交换后的两项等价于： $b_i$ 与 $a_{i+1} b_{i+1}$

因为 $a_i, a_{i+1} \ge 1$ ，显然有：

a_i b_i \ge b_i, \quad a_{i+1} b_{i+1} \ge b_{i+1}

若满足：

a_i b_i \le a_{i+1} b_{i+1}

则有：

b_{i+1} \le a_{i+1} b_{i+1} \quad \text{且} \quad a_i b_i \le a_{i+1} b_{i+1}

故：

\max(b_{i+1}, a_i b_i) \le a_{i+1} b_{i+1} \le \max(b_i, a_{i+1} b_{i+1})

由此得到

M_1 \le M_2

。

这说明：只要大臣 $i$ 的 $a_i b_i$ 不超过大臣 $i+1$ 的 $a_{i+1} b_{i+1}$ ，大臣 $i$ 排在前面就绝不劣于排在后面。

3. 贪心策略

依据全序关系，我们只需将所有大臣按照 $a_i \times b_i$ 从小到大升序排序即可得到全局最优解。

最后按排好的顺序依次维护前缀乘积 $P$ 并计算每个大臣的 $\lfloor P / b_i \rfloor$ ，取最大值作为答案。

图示解析

以样例输入为例说明排序过程与各大臣所获金币的计算：

国王： $(a_0=1, b_0=1)$
大臣 1： $(a=2, b=3) \implies a \times b = 6$
大臣 2： $(a=7, b=4) \implies a \times b = 28$
大臣 3： $(a=4, b=6) \implies a \times b = 24$

按照 $a \times b$ 升序排序后的队伍如下表所示：

排位	人员	$(a, b)$	$a \times b$	前面所有人的左手乘积 $P$	获得金币 $\lfloor P / b \rfloor$
0	国王	$(1, 1)$	-	-	-
1	大臣 1	$(2, 3)$	6	$1$	$\lfloor 1 / 3 \rfloor = 0$
2	大臣 3	$(4, 6)$	24	$1 \times 2 = 2$	$\lfloor 2 / 6 \rfloor = 0$
3	大臣 2	$(7, 4)$	28	$1 \times 2 \times 4 = 8$	$\lfloor 8 / 4 \rfloor = 2$

所有大臣获得金币的最大值为 $2$ 。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 10:25
# update_at: 2026-10-01 10:25

import sys


def solve() -> None:
    tokens = sys.stdin.buffer.read().split()
    if not tokens:
        return
    data = iter(map(int, tokens))
    n = next(data)            # 大臣人数
    a0, b0 = next(data), next(data)  # 国王的左、右手
    # 每个大臣按 a * b 升序排序
    ministers = sorted(
        [(next(data), next(data)) for _ in range(n)],
        key=lambda m: m[0] * m[1],
    )

    prefix_prod = a0
    ans = 0
    for a, b in ministers:
        ans = max(ans, prefix_prod // b)
        prefix_prod *= a

    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:26
 * update_at: 2026-10-06 14:26
 */

// 国王游戏：邻项交换法证明按 a*b 升序排序最优，
// 高精度维护前面所有人左手数的乘积，逐个算 floor(P / b) 取最大值。

#include <cstdio>
#include <iostream>
#include <algorithm>

typedef long long ll;

const int MAXN = 1005;      // 大臣人数上限
const int LEN  = 4500;      // 高精度数的最大位数（1000 个 a 相乘，每个 < 10^4，最多约 4000 位）

// 高精度非负整数，低位在前，存十进制位
struct Big {
    int len;
    int d[LEN];
    Big() : len(1) {
        for (int i = 0; i < LEN; i++) d[i] = 0;
    }
};

// 高精度乘以普通整数（a < 10^4，进位用 ll 防溢出）
Big mul_small(const Big &x, ll a) {
    Big y;
    ll carry = 0;
    for (int i = 0; i < x.len; i++) {
        ll cur = (ll)x.d[i] * a + carry;
        y.d[i] = cur % 10;
        carry = cur / 10;
    }
    y.len = x.len;
    while (carry > 0) { // 补齐剩余进位
        y.d[y.len] = carry % 10;
        carry /= 10;
        y.len++;
    }
    return y;
}

// 高精度除以普通整数，返回商（向下取整）
Big div_small(const Big &x, ll b) {
    Big q;
    ll rem = 0;
    for (int i = x.len - 1; i >= 0; i--) { // 从高位往低位做除法
        rem = rem * 10 + x.d[i];
        q.d[i] = rem / b;
        rem %= b;
    }
    q.len = x.len;
    while (q.len > 1 && q.d[q.len - 1] == 0) q.len--; // 去掉前导零
    return q;
}

// 比较：返回 true 表示 a > b
bool is_greater(const Big &a, const Big &b) {
    if (a.len != b.len) return a.len > b.len;
    for (int i = a.len - 1; i >= 0; i--)
        if (a.d[i] != b.d[i]) return a.d[i] > b.d[i];
    return false;
}

struct Minister {
    ll a, b;
    ll key() const { return a * b; } // 排序关键字 a * b
};

Minister ms[MAXN]; // ms[i] 表示第 i 位大臣的左右手数字
int n;             // 大臣人数（n ≤ 1000，int 足够，可直接做数组下标）

// 按左右手乘积 a*b 从小到大排序（邻项交换法推出的贪心序）
bool cmp_minister(const Minister &x, const Minister &y) {
    return x.key() < y.key();
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    std::cin >> n;
    ll a0, b0;
    std::cin >> a0 >> b0; // 国王的左右手，右手 b0 不参与计算
    for (int i = 1; i <= n; i++)
        std::cin >> ms[i].a >> ms[i].b;

    std::sort(ms + 1, ms + 1 + n, cmp_minister);

    Big prefix;      // 前缀乘积：排在当前大臣前面所有人（含国王）左手数的乘积
    prefix.d[0] = 1; // 初始为 1，先乘上国王左手数 a0
    prefix = mul_small(prefix, a0);

    Big ans; // 所有大臣中获得金币数的最大值
    for (int i = 1; i <= n; i++) {
        Big reward = div_small(prefix, ms[i].b); // 该大臣获得的金币：floor(P / b)
        if (is_greater(reward, ans)) ans = reward;
        prefix = mul_small(prefix, ms[i].a);
    }

    for (int i = ans.len - 1; i >= 0; i--)
        std::cout << ans.d[i];
    std::cout << std::endl;

    return 0;
}

复杂度

时间复杂度：
1. 排序的时间复杂度为 $O(n \log n)$ 。
2. 遍历大臣计算前缀积与整除：在大整数运算下，数字位数为 $L \le 4000$ ，高精度乘以/除以单精度数值的单次复杂度为 $O(L)$ 。总时间复杂度为 $\sum_{i=1}^n O(i) = O(n^2)$ 。在 $n \le 1000$ 的约束下，计算耗时仅几十毫秒，远在 $1000\text{ ms}$ 时限内。
空间复杂度：存储大臣列表与数千位高精度整数仅需 $O(n)$ 空间，满足 $128\text{ MB}$ 内存限制。

总结

国王游戏是经典的“邻项微扰（微扰法/交换法）”证明贪心正确性的代表题型。通过考察相邻两个元素的交换对局部最大值的影响，消去无关项，提炼出仅与单个元素属性相关的排序关键字 $a_i \times b_i$ 。在实现层面，利用 Python 原生支持的高精度大整数可以极为简洁地完成大数连乘与整除。

目录

形式化题目

正解

思路

1. 邻项交换法推导

2. 比较两状态的最大值

3. 贪心策略

图示解析

代码

复杂度

总结