恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
[编程题][NOIP2012]国王的游戏
- 热度指数：543 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行包含一个整数 n ，表示大臣的人数。
第二行包含两个整数 a 和 b ，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 n 行，每行包含两个整数 a 和 b ，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
输出描述:
一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
示例1
输入
3 1 1 2 3 7 4 4 6
输出
2
说明
按 1 、 2 、 3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2 ；
按 1 、 3 、 2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2 ；
按 2 、 1 、 3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2 ；
按 2 、 3 、 1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9 ；
按 3 、 1 、 2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2 ；
按 3 、 2 、 1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9 。
因此，奖赏最多的大臣最少获得 2 个金币，答案输出 2 。
备注:
对于 20%的数据，有 1≤ n≤ 10,0 ＜ a,b ＜ 8 ；
对于 40%的数据，有 1≤ n≤20,0 ＜a,b＜8 ；对于 60%的数据，有 1≤ n≤100 ；对于 60%的数据，保证答案不超过 109 ；对于 100%的数据，有 1 ≤ n ≤1,000,0 ＜ a,b ＜ 10000 。
题目描述 恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣
展开全文
国王的游戏 https://ac.nowcoder.com/acm/problem/16561 恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队
展开全文
解题思路 贪心+快排对与相邻的两个大臣AB之间。先A后B，先B后A，只会改变这两个人最大值的取值，对其他人没有影响。那么假设第i个人和第i+1个人来看。前面积的值记为S。那么i在前就是，i+1在前就是可以明显发现并且那么如果我们要假设让i在前比i+1在前更好。就是最小值更小那么只有化简一下就是 按照
展开全文
思路：贪心+快排假设除了序列中相邻的两个大臣AB，其它大臣的位置都已经排好了。而AB的先后对前面和后面的结果都不会有影响，这里考虑A排前面最优的条件：左手数值用，右手数值用，表示AB前面大臣左手数值的乘积。1.A排前面时：,。2.B排前面时，,。3.。4.因为，所以不等式3需要满足，即。5.所以只要
展开全文
题目描述 恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：
展开全文
上述为引用洛谷题解
说明：高精度计算的板子应提前书写，贪心策略很重要
">#include<algorithm>//用到sort
#include<cstring>//用到memset
using namespace std;
const int MAXN = 1010, M
展开全文
">#include<stdio.h>
#include<algorithm>
using namespace std;
struct node{
int a,b;
char cnta[10000],all[10000];//cnta 为前面所有a的乘积的逆序 all为乘
展开全文
题意 恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有
展开全文
首先来看怎么确定高精度的位数，最多有1000各大臣，每个大臣左手数字最大为10000，所以相乘的最差结果就是10^4000，也就是至多是一个4000位的数（大臣手中数字不包括10000）。然后就是基本的高精度乘法和高精度除低精度的除法。
#include<bits/stdc++.h>
u
展开全文
问题信息
难度：
0条回答
3收藏
3671浏览
通过挑战的用户
-
2022-12-30 13:52:50
-
2022-11-23 10:18:53
-
2022-11-19 22:40:17
-
2022-10-02 22:08:35
-
2022-07-29 23:30:53
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
