首页 > 试题广场 >

[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

输入

输出

说明

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

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

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

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

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

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

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

备注:

算法知识视频讲解

丨阿伟丨

发表于 2025-09-10 10:08:11

PEEK123 [P1080] 国王游戏(简化版) 题目链接 PEEK123 [P1080] 国王游戏(简化版) 题目描述国王和位大臣玩游戏。国王的左右手分别写有整数，第位大臣左右手分别写有。所有大臣排成一队，国王站在最前面。对于排在第个位置的大臣，他能获得的金币数是。也就是说展开全文

YunBaichuan

发表于 2026-02-14 10:29:44

思路：贪心。题目强调了最小化最大值这个要求，不知道有没有同学用二分答案呢？但你仔细分析一下可以发现，这题不具备单调性，比如钱越多，越怎么样？没有单调性是用不了二分的。考虑暴力，直接全排列n个大臣，然后再一个一个算，那么时间复杂度就来到了惊人的，那肯定过不了。所以，正确的解法是贪心。首先第一直觉来说展开全文

DJ_Chan

发表于 2025-09-17 17:04:47

题目分析我们需要安排 n 个大臣的顺序，使得获得最多金币的大臣所获得的金币数尽可能少。金币计算公式对于第 i 个大臣，其金币数为：其中表示国王的左右手数字。贪心策略证明我们需要找到一种排序方式，使得所有大臣中金币数的最大值最小化。按升序排列是最优策略。数学证明考虑相邻两个大臣 i 和 j，且展开全文

bandiaoz

发表于 2025-08-08 21:32:14

题目链接 BISHI53 [P1080] 国王游戏(简化版) 题目描述国王左、右手分别写下两个整数；共有位大臣，第位大臣左、右手写下。国王站最前，其余大臣可任意排序。若某位大臣在队列中的相对位置为，则他获得的金币数为其中为队列中大臣的编号顺序。目标是通过调整大臣顺序，使“ 展开全文

虚静观复

发表于 2026-02-15 01:49:15

题目跳转： [P1080] 国王游戏(简化版) 贪心据题，在任意顺序的排列下，期望让得到最多金币的臣子得到的金币数最小。解题思路设当前累乘得到的积为，第i个臣子在左/右手写下的数字分别为、。首先我们根据题目得到第i个臣子能够得到的金币数量为：而对于所有臣子，我们希望能够让展开全文

GG了的退堂鼓鼓手很迷人

发表于 2025-11-06 22:27:42

#include <algorithm> #include <iostream> #include <vector> using namespace std; bool com(const pair<int,int>&a,const pair 展开全文

chenlan114

发表于 2026-02-14 09:58:07

#include<bits/stdc++.h> using namespace std; using ll=long long; const ll N=65; struct C{ ll a,b; bool operator<(const C& other) 展开全文

秋宇_

发表于 2026-02-14 11:34:28

#include<bits/stdc++.h> #define x first #define y second #define endl "\n" #define MAX INT_MAX #define LMAX LLONG_MAX #define ll long 展开全文

此在Dasein

发表于 2026-02-14 16:02:26

本题看似是一个全排列搜索问题，但的规模直接否定了暴力枚举的可能性（是天文数字）。问题的本质是最小化最大值（Min-Max），这是典型的贪心算法应用场景。我们需要寻找一种局部最优的排序策略，使得其能够直接推导出全局最优解。算法推导（微扰分析法）为了确定大臣们的排序规则，我们采用“邻项交换法” 展开全文