国王游戏

GitHub跳转原题关系图返回列表

交换论证：大臣按左右手数字之积 a_i×b_i 从小到大排队，最大奖赏最小；乘积用 Python 大整数顺扫一遍统计。

OJ: roj

题目 ID: 3599

难度:提高

标签:贪心排序数学

创建: 2026-10-02 09:53

更新: 2026-10-10 11:30

后置题目

roj 3021「Color a Tree」给树染色B 的两条关键观察都直接沿用 A 教的『交换相邻两人只影响这两人』这一步：先由 u 与前驱 w 交换只差 A[u]-A[w]、与轮数无关推出同在父块连续，再对相邻块做同样的交换推出按平均值降序，之后才叠加树约束下的块合并与按对计费增量。luogu P4823[TJOI2013] 拯救小矮人B 的第一步直接复用 A 教的邻项交换论证——同样只比较相邻两人、由局部换序不劣推出全局排序键（B 代码 cmp_dwarf 即按 a_i+b_i 排序），只是把排序键从 a_i×b_i 换成 a_i+b_i，之后再叠加 A 未教的前缀限制改写与大根堆「最多任务数」贪心。

形式化题目

国王写下一对整数 $(a_0, b_0)$ ，另有 $n$ 位大臣各写下一对整数 $(a_i, b_i)$ 。把 $n$ 位大臣排成一个排列 $p$ ，排在位置 $k$ 的大臣获得的金币数为

\left\lfloor \frac{\prod_{j<k} a_{p_j}}{b_{p_k}} \right\rfloor,

即排在他前面的所有人（含国王）左手数字的乘积除以他自己右手数字，向下取整。求一个排列，使获得金币最多的大臣所得最少，输出这个最小值。

样例：国王 $(1,1)$ ，三位大臣 $(2,3),(7,4),(4,6)$ 。按 $1,2,3$ 排列时各人得到 $\lfloor 1/3\rfloor=0$ 、 $\lfloor 2/4\rfloor=0$ 、 $\lfloor 14/6\rfloor=2$ ，最大值为 $2$ ，这就是答案。

排列	各大臣金币	最大值
$1,2,3$	$\lfloor 1/3\rfloor=0,\ \lfloor 2/4\rfloor=0,\ \lfloor 14/6\rfloor=2$	2
$2,3,1$	$\lfloor 1/6\rfloor=0,\ \lfloor 2/4\rfloor=0,\ \lfloor 14/3\rfloor=4$	4
$3,2,1$	$\lfloor 1/6\rfloor=0,\ \lfloor 4/4\rfloor=1,\ \lfloor 28/3\rfloor=9$	9

同一个样例换个排列最大值就从 $2$ 涨到 $9$ ：左手乘积越攒越大，靠后的人很容易被"撑爆"，所以谁站前面并不随意——这正是下面贪心要回答的问题。

暴力解法

思路

$n \leqslant 10$ 或 $n \leqslant 20$ 时直接枚举全排列：对每个排列从左往右累乘左手数字，算出每个人的金币数，取最大值；所有排列的最大值再取最小即为答案。前 $40\%$ 的数据（ $n \leqslant 20$ 、 $a,b<8$ ）都能轻松通过。

代码

暴力思路略（前 40% 的全排列枚举按上述思路用 itertools.permutations 即可，无独立教学价值，也不参与对拍，故不保留代码文件）。

复杂度

每个排列需要 $O(n)$ 次大整数乘除，共 $n!$ 个排列，总复杂度 $O(n \cdot n!)$ ，只适用于 $n \leqslant 10 \sim 20$ 。

瓶颈

瓶颈在于把 $n$ 个大臣的所有站法当成彼此独立的方案逐个尝试，完全没有利用"相邻两人交换后，其他人的金币数都不变"这一局部结构。所有最优排列里一定存在一个可以通过不断交换相邻元素得到的形态，因此只需弄清相邻两人谁站前面更好，就能一次性定下整支队伍的顺序。

正解

思路

先做一步关键观察：设某相邻两人的左手数、右手数分别为 $(a_i, b_i)$ 、 $(a_j, b_j)$ ，他们前面所有人（含国王）左手乘积为 $P$ 。交换这两个人，队伍里其他大臣面前的乘积不变，金币数不变；受影响的只有这两人的金币数：

位置	左手乘积	除以的右手数	金币数
$i$ 在前（原序）	$P$	$b_i$	$\left\lfloor P / b_i \right\rfloor$
$j$ 在后（原序）	$P \cdot a_i$	$b_j$	$\left\lfloor P a_i / b_j \right\rfloor$
$j$ 在前（交换后）	$P$	$b_j$	$\left\lfloor P / b_j \right\rfloor$
$i$ 在后（交换后）	$P \cdot a_j$	$b_i$	$\left\lfloor P a_j / b_i \right\rfloor$

我们要证：当 $a_i b_i \leqslant a_j b_j$ 时，保持 $i$ 在前不会让两人的最大金币数变大，即

\max\left(\left\lfloor \frac{P}{b_i} \right\rfloor, \left\lfloor \frac{P a_i}{b_j} \right\rfloor\right) \leqslant \max\left(\left\lfloor \frac{P}{b_j} \right\rfloor, \left\lfloor \frac{P a_j}{b_i} \right\rfloor\right).

$\lfloor\cdot\rfloor$ 单调不减，先比较去掉取整的实数值。两边同乘正数 $\dfrac{b_i b_j}{P}$ （ $P > 0$ ），消去公共因子，等价于

\max\left(b_j,\ a_i b_i\right) \leqslant \max\left(b_i,\ a_j b_j\right).

由 $a_i, a_j \geqslant 1$ 知 $b_j \leqslant a_j b_j$ 、 $b_i \leqslant a_i b_i$ 。若 $a_i b_i \leqslant a_j b_j$ ，则左边两项 $b_j \leqslant a_j b_j$ 与 $a_i b_i \leqslant a_j b_j$ 都不超过右边，不等式成立；反之若 $a_i b_i > a_j b_j$ ，则左边 $\geqslant a_i b_i$ ，而右边两项 $b_i \leqslant a_i b_i$ 、 $a_j b_j < a_i b_i$ 都严格更小，此时交换两人反而严格更优。综合两种情况：乘积小的人站前面总是不更差。

于是把所有大臣按 $a_i \times b_i$ 从小到大排序（乘积相同时任意顺序均可——此时两种站法同样好），依次排成一排，国王仍在最前面。任意排列都能经有限次相邻交换变成这个排序，而每次交换都不让最大值变大，所以排序后的队伍就是最优队伍之一。

最后扫一遍排序结果：维护一个累乘变量（初始为国王左手数 $a_0$ ），第 $k$ 位大臣的金币数为 $\lfloor$ 当前乘积 $/ b_k \rfloor$ ，取最大值，随后把他的左手数乘进累乘变量。

代码

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/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int BASE = 1000000000;
struct BigInt {
    vector<int> d;
    int sign;
    BigInt(ll x = 0) { sign = 1; if (x < 0) { sign = -1; x = -x; } if (x == 0) sign = 0; while (x) { d.push_back(x % BASE); x /= BASE; } }
};
void trim(BigInt &a) { while (!a.d.empty() && a.d.back() == 0) a.d.pop_back(); if (a.d.empty()) a.sign = 0; }
BigInt read_big(string s) { BigInt a; a.d.clear(); a.sign = 1; int pos = 0; if (s[0] == '-') { a.sign = -1; pos = 1; } for (int i = s.size(); i > pos; i -= 9) { int l = max(pos, i - 9); int x = 0; for (int j = l; j < i; j++) x = x * 10 + s[j] - '0'; a.d.push_back(x); } trim(a); return a; }
int cmp_abs(const BigInt &a, const BigInt &b) { if (a.d.size() != b.d.size()) return a.d.size() < b.d.size() ? -1 : 1; for (int i = (int)a.d.size() - 1; i >= 0; i--) if (a.d[i] != b.d[i]) return a.d[i] < b.d[i] ? -1 : 1; return 0; }
BigInt add_abs(const BigInt &a, const BigInt &b) { BigInt c; c.sign = 1; int n = max(a.d.size(), b.d.size()); c.d.assign(n, 0); ll carry = 0; for (int i = 0; i < n; i++) { ll v = carry; if (i < (int)a.d.size()) v += a.d[i]; if (i < (int)b.d.size()) v += b.d[i]; c.d[i] = v % BASE; carry = v / BASE; } if (carry) c.d.push_back(carry); trim(c); return c; }
BigInt sub_abs(const BigInt &a, const BigInt &b) { BigInt c; c.sign = 1; c.d.assign(a.d.size(), 0); ll borrow = 0; for (int i = 0; i < (int)a.d.size(); i++) { ll v = (ll)a.d[i] - borrow - (i < (int)b.d.size() ? b.d[i] : 0); if (v < 0) { v += BASE; borrow = 1; } else borrow = 0; c.d[i] = v; } trim(c); return c; }
BigInt add_big(BigInt a, BigInt b) { if (a.sign == 0) return b; if (b.sign == 0) return a; if (a.sign == b.sign) { BigInt c = add_abs(a, b); c.sign = a.sign; return c; } int cmp = cmp_abs(a, b); if (cmp == 0) return BigInt(0); if (cmp > 0) { BigInt c = sub_abs(a, b); c.sign = a.sign; return c; } BigInt c = sub_abs(b, a); c.sign = b.sign; return c; }
BigInt mul_int(BigInt a, ll m) { if (a.sign == 0 || m == 0) return BigInt(0); if (m < 0) { a.sign = -a.sign; m = -m; } BigInt c; c.sign = a.sign; c.d.assign(a.d.size(), 0); ll carry = 0; for (int i = 0; i < (int)a.d.size(); i++) { __int128 v = (__int128)a.d[i] * m + carry; c.d[i] = (ll)(v % BASE); carry = (ll)(v / BASE); } while (carry) { c.d.push_back(carry % BASE); carry /= BASE; } trim(c); return c; }
BigInt div_int(BigInt a, ll m) { BigInt c; c.sign = a.sign; c.d.assign(a.d.size(), 0); ll rem = 0; for (int i = (int)a.d.size() - 1; i >= 0; i--) { __int128 cur = (__int128)rem * BASE + a.d[i]; c.d[i] = (ll)(cur / m); rem = (ll)(cur % m); } trim(c); return c; }
bool less_big(const BigInt &a, const BigInt &b) { if (a.sign != b.sign) return a.sign < b.sign; if (a.sign == 0) return false; int cmp = cmp_abs(a, b); return a.sign > 0 ? cmp < 0 : cmp > 0; }
bool is_zero(const BigInt &a) { return a.sign == 0; }
ostream& operator<<(ostream &os, const BigInt &a) { if (a.sign == 0) { os << 0; return os; } if (a.sign < 0) os << '-'; int n = a.d.size(); os << a.d[n - 1]; for (int i = n - 2; i >= 0; i--) os << setw(9) << setfill('0') << a.d[i]; return os; }

struct Person{ll a,b;};
bool cmp_person(const Person &x, const Person &y){ return x.a * x.b < y.a * y.b; }
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; if(!(cin>>n)) return 0; string sa,sb; cin>>sa>>sb; BigInt prod=read_big(sa), best(0); vector<Person> p(n); for(int i=0;i<n;i++) cin>>p[i].a>>p[i].b; sort(p.begin(),p.end(),cmp_person); for(int i=0;i<n;i++){ BigInt cur=div_int(prod,p[i].b); if(less_big(best,cur)) best=cur; prod=mul_int(prod,p[i].a); } cout<<best<<'\n'; return 0; }

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#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def solve() -> None:
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))
    a, b = int(next(it)), int(next(it))          # 国王的左右手数字

    # 大臣按 a_i * b_i 从小到大排：交换相邻两人不会让最大奖赏变大
    ministers = sorted(
        ((int(next(it)), int(next(it))) for _ in range(n)),
        key=lambda p: p[0] * p[1],
    )

    best = 0
    for ai, bi in ministers:
        best = max(best, a // bi)  # 队列里排在他前面的人左手的乘积
        a *= ai

    print(best)


if __name__ == "__main__":
    solve()

复杂度

排序 $O(n \log n)$ ；扫一遍的过程中，累乘变量最多达到 $(10^4)^{1001}$ 量级（约 $10^{4000}$ ，上千位的十进制大数）。Python 的整数乘除法天然支持大数，一次大数运算约 $O(D)$ （ $D$ 为位数），总复杂度 $O(n \log n + n \cdot D)$ ；对 $n \leqslant 1000$ 绰绰有余，远低于 $1000\text{ ms}$ 的限制。若在 C++ 中实现，需要手写高精度乘大整数、除小整数（压位存储），同样是 $O(n \log n + n \cdot D)$ 。

总结

核心是邻项交换排序（交换论证）：只比较相邻两人，推出" $a_i b_i$ 小的站前面"这一全局排序依据，与"区间调度按右端点排序"是同一套方法论。
影响某人金币数的只有他前面的左手乘积和他自己的右手数，交换相邻两人不影响其他人，这是整个论证成立的支点。
用 Python 做这类高精度贪心题非常划算：大整数乘除开箱即用，代码只剩排序加一次线性扫描。

国王游戏

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

代码

复杂度

总结