51Testing软件测试论坛

标题: 做题记（4）P1080 国王游戏 [打印本页]

作者: 乐哈哈yoyo 时间: 2019-2-1 15:02
标题: 做题记（4）P1080 国王游戏
今天，做了洛谷上的P1080 国王游戏，题目如下：
题目描述
恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n nn 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
输入输出格式
输入格式：
第一行包含一个整数 n，表示大臣的人数。
第二行包含两个整数a和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 $n $行，每行包含两个整数a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
输出格式：
一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
作为一个蒟蒻，这道题把我难住了，想了半天脑子都要炸了还想不出来。后来，我看了一下洛谷的题解，找到一点思路。根据题解中的证明，a×b乘积越小的大臣越应该排在前面。那么，这是为何？理由如下：

左手右手
X1
Ai Bi
X2
Aj Bj
设从国王开始到第i位以前的乘积为X1，第i位左手为Ai，右手为Bi，第i位以后到第j位以前乘积为X2，第j位左手为Aj，右手为Bj,。
由题意
第i位的金币数为Mi=X1/Bi
第j位的金币数为Mj=X1×Ai×X2/Bj
因为金币数M1=max（Mi,Mj）
所以M1=max（X1/Bi,X1×Ai×X2/Bj)
现将i和j位置交换
同理可得
Mi=X1×Aj×X2/Bi
Mj=X1/Bj
M2=max（X1×Aj×X2/Bi，X1/Bj）
当M2>M1时
max（X1×Aj×X2/Bi，X1/Bj）>max（X1/Bi,X1×Ai×X2/Bj)
因为X1×Aj×X2/Bi>X1/Bi,X1/Bj<X1×Ai×X2/Bj
所以X1×Aj×X2/Bi>X1×Ai×X2/Bj
化简得Aj×Bj>Ai×Bi;
当M2<M1时
max（X1×Aj×X2/Bi，X1/Bj）<max（X1/Bi,X1×Ai×X2/Bj)
因为X1×Aj×X2/Bi>X1/Bi,X1/Bj<X1×Ai×X2/Bj
所以X1×Aj×X2/Bi<X1×Ai×X2/Bj
化简得Aj×Bj<Ai×Bi;
所以a×b乘积越小越应该排在前面。

但是，光这样做还是不行的，还要用高精度哦（巨坑）。
---------------------

欢迎光临 51Testing软件测试论坛 (http://bbs.51testing.com/)