题目大意 有 nnn 只怪兽，每只怪兽都有生命值 hih_ihi 和攻击力 pip_ipi ，超能战士每次可以对所有活着的怪兽造成 kkk 点伤害。 怪兽会在每次超能战士攻击后进行反击，活着最弱的怪兽会降低超能战士攻击伤害，降为 k−pik - p_ik−pi 题意分析 求问超能战士能不能消灭所有的怪兽 解题思路 从题中可以发现，超能战士的攻击力 kkk 同时可以看做是超能战士的血量，当 k≤0k \le 0k≤0 的时候，如果场上还有怪兽，则不能消灭所有怪兽。 超能战士每进行一次攻击可以消灭所有当前血量 ≤k\le k≤k 的怪兽，我们可以模拟这个过程直到超能战士的攻击力 ≤0\le 0≤0，所以重点考虑怎么去模拟这个过程，如果用暴力的方式，一遍一遍让怪兽的血量减去 kkk，那么复杂度为 O(n⋅k)O(n \cdot k )O(n⋅k)，超时！ 实际上我们只需要找到第一个不能被杀死的怪兽，即第一个血量 >k\gt k>k 的怪兽。 我们可以先按照血量从小到大排序，我们记找到第一个血量 >k\gt k>k 怪兽的下标为 iii，那么 <i\lt i<i 的怪兽都视为死亡，≥i\ge i≥i的怪兽都为存活。由于血量是有序的了，满足单调性，我们可以使用二分。由于怪兽的血量是会变化的，在二分的时候要将怪兽的血量减去超能战士累积攻击的伤害。 我们还有个问题没有解决，如何在存活的怪兽中，找到最弱的，即攻击力最小的。存活的下标区间为 [i,n)[i,n)[i,n)，我们可以贪心最小值，倒着遍历不断看右边的最小值与当前值哪一个更小，来维护一个最小值数组。 时间复杂度解析 维护小最值数组，需要遍历所有怪物，复杂度为 O(n)O(n)O(n) 查找第一个不能杀死的怪物，用到了二分，直到 k≤0k \le 0k≤0 时，结束模拟过程。复杂度为 O(n⋅log⁡2n)O(n \cdot \log_{2} n)O(n⋅log2 n) 代码演示