首页 > 试题广场 >

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

[编程题][P1080] 国王游戏(简化版)

热度指数：743 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 龙国国庆之际，国王邀请 $n$ 位大臣参与一起玩一个游戏。国王与每位大臣都会在左、右手各写一整数：国王分别写下了 $(a_0,b_0)$ ；此后第 $i$ 位大臣写下 $(a_i,b_i)$ 。

$\hspace{15pt}$ 现在国王站在最前方，其余大臣依次排成一行。排定顺序后，第 $i$ 位大臣（排在队伍中的相对顺序）能得到的金币数为 $\displaystyle \left\lfloor \frac{\prod_{j=0}^{i-1} a_j}{b_i}\right\rfloor$ ，其中 $a_0=A$ 表示国王左手的数字。

$\hspace{15pt}$ 国王希望通过调整大臣的站位顺序（相对顺序可任意改变，国王位置固定在最前），使得 获得金币最多 的大臣得到的金币数尽可能小。

输入描述:

第一行输入整数 ——大臣人数。
第二行输入两个整数 ——国王左、右手的数字。
随后  行，第  行输入两个整数 ——第  位大臣左、右手的数字。

输出描述:

输出一个整数，表示在最优站位下，获奖最多的大臣所能获得的最小金币数。
数据保证答案不超过 ；

示例1

输入

输出

说明

按 、、 这样排列队伍，获得奖赏最多的大臣所获得金币数为 ；

按 、、 这样排列队伍，获得奖赏最多的大臣所获得金币数为 ；

按 、、 这样排列队伍，获得奖赏最多的大臣所获得金币数为 ；

按、、这样排列队伍，获得奖赏最多的大臣所获得金币数为 ；

按 、、这样排列队伍，获得奖赏最多的大臣所获得金币数为 ； 

按、、 这样排列队伍，获得奖赏最多的大臣所获得金币数为 。

因此，奖赏最多的大臣最少获得  个金币，答案输出 。

备注:

算法知识视频讲解

pandaC222

import sys
input = sys.stdin.readline
n = int(input())
a0, b0 = map(int, input().split())
lst=[]
for i in range(n):
    ai, bi = map(int, input().split())
    lst.append((ai,bi))
lst.sort(key = lambda x: x[0] * x[1])
ans=-1
pre=a0
for i in range(n):
    ans=max(pre//lst[i][1], ans)
    pre*=lst[i][0]
print(ans)

发表于 2026-02-14 08:06:45 回复(1)