Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom11月前

07/16
08:48
模拟 贪心

[bzoj 3709] [PA2014]Bohater

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 在一款电脑游戏中,你需要打败n只怪物(从1到n编号)。为了打败第i只怪物,你需要消耗d[i]点生命值,但怪物死后会掉落血药,使你恢复a[i]点生命值。任何时候你的生命值都不能降到0(或0以下)。请问是否存在一种打怪顺序,使得你可以打完这n只怪物而不死掉

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行两个整数n,z(1<=n,z<=100000),分别表示怪物的数量和你的初始生命值。
接下来n行,每行两个整数d[i],a[i](0<=d[i],a[i]<=100000)

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

第一行为TAK(是)或NIE(否),表示是否存在这样的顺序。
如果第一行为TAK,则第二行为空格隔开的1~n的排列,表示合法的顺序。如果答案有很多,你可以输出其中任意一个。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

3 5
3 1
4 8
8 3

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

TAK
2 3 1

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

贪心考虑,首先,可以回血的怪肯定排在前面。因为要一直活着,所以要按杀怪的消耗从小到大排序。然后杀怪掉血的可以反过来看,最后的血量last一定是确定的,杀怪就变成了先把血药吐出来然后补上杀怪消耗的血量,所以从后往前应该按照回血量从小到大排序,正过来也就是按照回血量从大到小排序,然后模拟一遍打怪的过程就好了。

 

[bzoj 3709] [PA2014]Bohater