LeetCode 题解工作台
对 Bob 造成的最少伤害
给你一个整数 power 和两个整数数组 damage 和 health ，两个数组的长度都为 n 。 Bob 有 n 个敌人，如果第 i 个敌人还活着（也就是健康值 health[i] > 0 的时候），每秒钟会对 Bob 造成 damage[i] 点 伤害。 每一秒中，在敌人对 Bob 造成伤害…
3
题型
0
代码语言
3
相关题
当前训练重点
困难 · 贪心·invariant
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个整数 power 和两个整数数组 damage 和 health ，两个数组的长度都为 n 。
Bob 有 n 个敌人，如果第 i 个敌人还活着（也就是健康值 health[i] > 0 的时候），每秒钟会对 Bob 造成 damage[i] 点 伤害。
每一秒中，在敌人对 Bob 造成伤害 之后 ，Bob 会选择 一个 还活着的敌人进行攻击，该敌人的健康值减少 power 。
请你返回 Bob 将 所有 n 个敌人都消灭之前，最少 会受到多少伤害。
示例 1：
输入：power = 4, damage = [1,2,3,4], health = [4,5,6,8]
输出：39
解释：
- 最开始 2 秒内都攻击敌人 3 ，然后敌人 3 会被消灭，这段时间内对 Bob 的总伤害是
10 + 10 = 20点。 - 接下来 2 秒内都攻击敌人 2 ，然后敌人 2 会被消灭，这段时间内对 Bob 的总伤害是
6 + 6 = 12点。 - 接下来 1 秒内都攻击敌人 0 ，然后敌人 0 会被消灭，这段时间内对 Bob 的总伤害是
3点。 - 接下来 2 秒内都攻击敌人 1 ，然后敌人 1 会被消灭，这段时间内对 Bob 的总伤害是
2 + 2 = 4点。
示例 2：
输入：power = 1, damage = [1,1,1,1], health = [1,2,3,4]
输出：20
解释：
- 最开始 1 秒内都攻击敌人 0 ，然后敌人 0 会被消灭，这段时间对 Bob 的总伤害是
4点。 - 接下来 2 秒内都攻击敌人 1 ，然后敌人 1 会被消灭，这段时间对 Bob 的总伤害是
3 + 3 = 6点。 - 接下来 3 秒内都攻击敌人 2 ，然后敌人 2 会被消灭，这段时间对 Bob 的总伤害是
2 + 2 + 2 = 6点。 - 接下来 4 秒内都攻击敌人 3 ，然后敌人 3 会被消灭，这段时间对 Bob 的总伤害是
1 + 1 + 1 + 1 = 4点。
示例 3：
输入：power = 8, damage = [40], health = [59]
输出：320
提示：
1 <= power <= 1041 <= n == damage.length == health.length <= 1051 <= damage[i], health[i] <= 104
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for knowledge of greedy algorithms and sorting techniques.
- question_mark
Check for understanding of how sorting and custom comparators can optimize decision-making.
- question_mark
Evaluate the candidate’s ability to manage and manipulate arrays effectively.
常见陷阱
外企场景- error
Failing to sort the enemies properly, leading to suboptimal attack orders.
- error
Not correctly implementing the greedy approach by attacking the wrong enemy first.
- error
Overcomplicating the solution or failing to recognize that sorting is the key to an efficient approach.
进阶变体
外企场景- arrow_right_alt
What if the power is not sufficient to defeat all enemies in one attack?
- arrow_right_alt
How would the solution change if Bob could attack multiple enemies simultaneously?
- arrow_right_alt
What would be the effect of reducing the power of Bob's attacks over time?