题解：策略打怪
2026-09-07 21:33:58
发布于：上海
2阅读
0回复
0点赞
https://www.xmoj.tech/problem.php?cid=10562&pid=0
一道比较有意思的题目。
初步思路：
首先不难发现怪物一共分为两类。
1.打掉之后可以回血的怪物
2.打掉之后会掉血的怪物
那么大策略一定是先打掉可以回血的怪物。
打回血的怪物的顺序是：先打消耗生命数值小的先去弄。
那么关键点在于如何去打会掉血的怪物：
初步有可能是有一些奇奇怪怪的想法。比如说，排序d[i]从小到大/从大到小。
这时发现一个性质：事实上最后你减掉的血量，加上的血量是一样的。
从不能回血那一刻开始，所有的怪物都只能让你掉血。
那么打不过就是打不过。
这时，再去造一个小样例，比如说我们此时有两个怪物：
1999 0
3 2
然后目前的血量是2001，那么如果先选一后选二就会挂，先选二候后一就能活。
这个时候“先把好的状态多的血量拿去打大怪”这个策略就无法成立。
为什么？因为回的血量不够。
那么我们就可以进行一些猜测。比如说：对a[i]进行从大到小排序。
证明：
if now-d[2]+a[2]<d[1] -> now-d[1]+a[1]<d[2]
now+a[2]<d[1]+d[2] ->now+a[1]<d[2]+d[1]
（a[2]>a[1]）
这里空空如也
有帮助，赞一个