Skip to content

Latest commit

 

History

History

1996.The-Number-of-Weak-Characters-in-the-Game

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

1996.The-Number-of-Weak-Characters-in-the-Game

对于这种涉及两种属性的题目,常见的思想就是固定一个属性,探索另外一个属性。

对于本题,所谓“固定一个属性”,就是指将所有人按照攻击力排序。这样的话,靠前的人自然地就会比靠后的人的武力值更低(暂不考虑属性值相同的情况),这样就简化了我们的任务。我们只需要在这个序列中查看有多少靠前的人的防御值也比靠后的人低即可。我们可以用一个栈,维护一个递减的防御力。如果新元素的防御力高,那么栈顶元素都是弱角色(因为攻击力和防御力都不及后来的新元素),可以不断退栈直至防御力不输给新元素。可以想象,只有递增的攻击力(排序)同时搭配递减的防御力(栈),才能保证序列的增长和元素的共存。否则就需要栈的弹出。

本题有一个特殊的情况需要处理,就是相同攻击力的元素,怎么保证低防御力的被高防御力的所消灭。这里用到了和354.Russian Doll Envelopes一样的技巧,将相同攻击力的人按照防御力从大到小排列。这样这些人逐个加入栈的时候,就不会触发弹栈操作。