用相邻交换证明按 a*b 升序排列大臣，Python 大整数直接维护前缀左手乘积。
OJ: luogu
题目 ID: P1080
难度:普及+/提高
标签:贪心排序高精度python
日期: 2026-06-22 20:40
题意
国王固定在队首，后面有 n 位大臣。每个人有左手数 a 和右手数 b。某位大臣获得的金币数是他前面所有人的左手数乘积除以自己的右手数，向下取整。要求重新排列大臣，使获得金币最多的大臣的金币数尽量小。
思路
先看一个小数据暴力：
cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10;
struct Person {
long long left_num;
long long right_num;
};
int n;
Person king, people[MAXN];
int order_id[MAXN];
__int128 calc_order() {
__int128 product = king.left_num;
__int128 worst = 0;
for (int i = 0; i < n; i++) {
int id = order_id[i];
worst = max(worst, product / people[id].right_num);
product *= people[id].left_num;
}
return worst;
}
void print_int128(__int128 x) {
if (x == 0) {
cout << 0 << '\n';
return;
}
string s;
while (x > 0) {
s.push_back((char)('0' + x % 10));
x /= 10;
}
reverse(s.begin(), s.end());
cout << s << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
cin >> king.left_num >> king.right_num;
for (int i = 0; i < n; i++) {
cin >> people[i].left_num >> people[i].right_num;
order_id[i] = i;
}
__int128 ans = -1;
do {
__int128 now = calc_order();
if (ans == -1 || now < ans) {
ans = now;
}
} while (next_permutation(order_id, order_id + n));
print_int128(ans);
return 0;
}暴力枚举所有排列，只能验证小数据。
正解用相邻交换。考虑相邻两个大臣 x=(a_x,b_x)、y=(a_y,b_y)，设他们前面左手乘积为 P。
若顺序是 x,y，这两人的金币上界来自：
text
P / b_x
P * a_x / b_y若顺序是 y,x，对应为：
text
P / b_y
P * a_y / b_x整理可以得到：当 a_x * b_x <= a_y * b_y 时，把 x 放在 y 前面不会更差。因此按 a*b 升序排序。
排序后从前到后模拟即可。Python 的整数是任意精度，不需要手写高精度乘除。
Python 知识
ministers.sort(key=lambda item: item[0] * item[1])按a*b排序。- Python
int自动支持大整数，本题可以直接维护prefix *= left。 prefix // right是整数除法，对应题目中的向下取整。
代码
python
import sys
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
king_left = data[1]
ministers = []
pos = 3
for _ in range(n):
left, right = data[pos], data[pos + 1]
pos += 2
ministers.append((left, right))
ministers.sort(key=lambda item: item[0] * item[1])
prefix = king_left
answer = 0
for left, right in ministers:
coins = prefix // right
if coins > answer:
answer = coins
prefix *= left
print(answer)
if __name__ == "__main__":
main()复杂度
排序复杂度是 D，模拟乘除约为
空间复杂度是
总结
排序依据不是单独的左手数或右手数，而是相邻交换推出的 a*b。Python 版本最大的优势是可以直接使用大整数。