如何答这题?唐山一中NOIP2005模拟赛(2)第二题2.魔兽争霸(war.pas)小x正在销魂地玩魔兽他正控制着死亡骑士和n个食尸鬼(编号1～n)去打猎死亡骑士有个魔法,叫做“死亡缠绕”,可以给食尸鬼补充HP

Question

如何答这题?唐山一中NOIP2005模拟赛(2)第二题
2.魔兽争霸(war.pas)
小x正在销魂地玩魔兽
他正控制着死亡骑士和n个食尸鬼(编号1～n)去打猎
死亡骑士有个魔法,叫做“死亡缠绕”,可以给食尸鬼补充HP
战斗过程中敌人会对食尸鬼实施攻击,食尸鬼的HP会减少
小x希望随时知道自己部队的情况,即HP值第k多的食尸鬼有多少HP,以便决定如何施放魔法
请同学们帮助他:)
小x向你发出3种信号：（下划线在输入数据中表现为空格）
A_i_a表示敌军向第i个食尸鬼发出了攻击,并使第i个食尸鬼损失了a点HP,如果它的HP

Answer 1

看到这数据规模,就想到应该是一个log级的算法.将输入数据排序.对于每次修改生命值,都将改变后的数值进行二分查找,找到它合适的位置然后将整个数据重新处理,由于数据随机生成,所以不用考虑算法退化的问题.（除非倒了血霉）