[贪心]国王游戏

冲冲冲,贪心题单的最后一道题

洛谷P1080 国王游戏

题目描述

恰逢HH国国庆,国王邀请nn位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这nn位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数nn,表示大臣的人数。

第二行包含两个整数aabb,之间用一个空格隔开,分别表示国王左手和右手上的整数。

接下来nn行,每行包含两个整数aabb,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。

输出格式

一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

贪心策略分析

这种公式类的算法,我第一个想到的就是用列式子求策略。如果不大熟悉这种求策略的方法,可以看看那简化版的:打怪兽

n=2n=2,国王手上的为a0b0a_0 b_0,两个大臣手里的是a1b1a_1 b_1a2b2a_2 b_2。现在我们要判断这两个大臣的谁在前更优,也就是比较两种情况。

第一种:
a0a_0 b0b_0
a1a_1 b1b_1
a2a_2 b2b_2

这样最后一个大臣所拿到的金币数为:

a0×a1÷b2a_0\times a_1\div b_2

第二种:
a0a_0 b0b_0
a2a_2 b2b_2
a1a_1 b1b_1

这样最后一个大臣所拿到的金币数为:

a0×a2÷b1a_0\times a_2\div b_1

我们现在就是要判断这两种情况哪个最少,也就是比较

if(a0×a1÷b2<a0×a2÷b1)if(a_0\times a_1\div b_2<a_0\times a_2\div b_1)

移一下项可以得到

if(a1×b1<a2×b2)if(a_1\times b_1<a_2\times b_2)

这样就很明显了,就是要比较每个大臣的aabb的乘积的大小,小的往前排就好了。

文章作者: Tim
文章链接: http://itstim.xyz/King/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Tim's Blog
支付宝恰饭打赏
微信恰饭打赏