How can we effectively defeat the enemy in UVALive7146 challenge?

本文共计830个文字，预计阅读时间需要4分钟。

题目链接+题目+链接题目+见链接题目解析+知识点：贪婪，STL。首先，要确保我方军队能消灭对方军队，因为只有这样才行动。所以，我们需要从大到小排序攻击力，从小到大排序防御力，然后从大到小遍历。使用我方军队所对应的攻击力去消灭对方军队。

题目链接

题目

见链接。

题解

知识点：贪心，STL。

首先要保证我方军队能消灭对方军队才行，因此只要我们按攻击力从大到小排，对方按防御力从大到小排，从大到小遍历，用我方所有攻击力大于敌方目前防御力军队中的一个打，就能保证对方小的防御力不会先把我方大的攻击力用掉，导致对方大的防御力没有办法消灭，即能消灭就一定消灭，不能就一定不能返回 \(-1\)。

现在考虑保证我方被消灭最少，发现如果在我方攻击力大于对方防御力的军队里面选，一定优先选择防御力刚好大于对方攻击力的军队，这样就可以保证大的防御力能保留，小的防御力不会被消灭；但如果最大的防御力都小于等于对方攻击力，那一定选择防御力最小的军队打，因为既然都会同归于尽，那么就让大的防御力保留，把最小的防御力同归于尽，保证后面有足够的防御力。因此我们这时候需要一个容器能够排序，查询，删除，插入，可以有相同元素，那么就要选择 \(multiset\) 存储我方军队防御力。