NOIP2012 DAY1 T2 国王游戏
题目描述
恰逢 H国国庆,国王邀请n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 n 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。
输入输出格式
输入格式:
第一行包含一个整数n,表示大臣的人数。
第二行包含两个整数 a和 b,之间用一个空格隔开,分别表示国王左手和右手上的整数。
接下来 nn行,每行包含两个整数a 和 b,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。
输出格式:
一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
假设最初存在3个仔[0,2],左右手分别标为ai,bi
那么a0,b0显然代表着国王,那么队列就可能是:
a0 b0
a1 b1
a2 b2
或者是
a0 b0
a2 b2
a1 b1
那么我知道对于第一种情况最大值是
max{a0/b1,a0*a1/b2}
对于第二种情况是
max{a0/b2,a0*a2/b1}
(请自动脑补下取整符号)
这样我们可以显然的知道:
a0*a1/b2 > a0/b2
a0*a2/b1 > a0/b1
这样问题就变成了
max{a0*a1/b2,a0*a2/b1}
然后我们假设存在a0*a1/b2 > a0*a2/b1
然后可以得到a1*b1 > a2*b2
就是说我们可以按所有人左右手的乘积大小从小到大排序。
但是这题要高精,所以我选择,去世
最新文章
- 常用数据库的驱动程序和Url地址
- Effective java笔记(七),通用程序设计
- C#怎样保证弹出窗体是唯一并居中显示
- X3850M2安装CertOS 7 KVM
- JAVA初学(1):值类型和引用类型的区别
- Xcode自定义Eclipse中常用的快捷键
- SQL Server 2014如何提升非在线的在线操作
- A.Kaw矩阵代数初步学习笔记 5. System of Equations
- C语言中关于字符串的一些常用函数
- 在js中获取query string 以及重写URL的函数
- java 与操作系统进程同步问题(一)————互斥问题
- HTTP 错误码
- JavaScript中常见的10个BUG及其修复方法
- centos 6.5 安装jdk1.8
- 使用FileZilla连接时超时,无法连接到服务器
- [C++]QString方法集
- PHP实现视频文件上传完整实例
- Number of Airplanes in the Sky
- 【Loadrunner接口测试】什么情况需要区分PC和手机端去做压测?
- nginx正则说明