DeepSeek LeetCode 3273. 对 Bob 造成的最少伤害 Go实现
这道题的核心是贪心 + 排序,难点在于推导出正确的排序规则。
💡 核心思路
· 策略一:集中攻击:选定一个敌人后,应连续攻击直至将其消灭。切换目标只会让已受攻击的敌人存活更久,造成更多伤害。
· 策略二:确定最优顺序:假设有两个敌人 A 和 B,消灭他们所需时间分别为 tA 和 tB。
· 先杀A再杀B的总伤害:tA * dA + (tA + tB) * dB
· 先杀B再杀A的总伤害:tB * dB + (tA + tB) * dA
· 当 tA * dB < tB * dA 时,先杀A更优。
· 化简得 tA / dA < tB / dB,即应优先消灭 时间/伤害 比值更小的敌人。
💻 Go 代码实现
```go
import "sort"
func minDamage(power int, damage []int, health []int) int64 {
n := len(damage)
type Enemy struct {
time int // 消灭所需秒数
damage int // 每秒伤害
}
enemies := make([]Enemy, n)
// 1. 计算每个敌人的消灭时间
for i := 0; i < n; i++ {
// 向上取整: (health[i] + power - 1) / power
t := (health[i] + power - 1) / power
enemies[i] = Enemy{time: t, damage: damage[i]}
}
// 2. 按 时间/伤害 升序排序 (核心)
sort.Slice(enemies, func(i, j int) bool {
// 避免浮点数,交叉相乘比较: t_i / d_i < t_j / d_j
// 等价于 t_i * d_j < t_j * d_i
return enemies[i].time*enemies[j].damage < enemies[j].time*enemies[i].damage
})
// 3. 计算总伤害
var totalDamage int64 = 0
var currentTime int64 = 0
for _, e := range enemies {
currentTime += int64(e.time)
totalDamage += currentTime * int64(e.damage)
}
return totalDamage
}
```
🧠 代码解读
· 计算消灭时间:(health[i] + power - 1) / power 是对 health[i] / power 的向上取整。
· 自定义排序:排序规则 enemies[i].time*enemies[j].damage < enemies[j].time*enemies[i].damage 是为了避免浮点数精度问题。
· 累加伤害:currentTime 记录了到当前敌人被消灭时总共经过的秒数。在这 currentTime 秒内,当前敌人每秒都会造成 e.damage 点伤害。
⏱️ 复杂度分析
· 时间复杂度: O(n log n),主要来自排序。
· 空间复杂度: O(n),用于存储敌人信息。
✅ 运行示例
以 power = 4, damage = [1,2,3,4], health = [4,5,6,8] 为例:
1. 计算每个敌人的消灭时间 t 和伤害 d,并排序。
2. 模拟过程:
· 杀敌人3(t=2, d=4):currentTime=2, 伤害 2*4=8
· 杀敌人2(t=2, d=3):currentTime=4, 伤害 4*3=12
· 杀敌人0(t=1, d=1):currentTime=5, 伤害 5*1=5
· 杀敌人1(t=2, d=2):currentTime=7, 伤害 7*2=14
3. 总伤害 8+12+5+14=39,与预期一致。
希望这个 Go 语言的实现能帮助你解决问题。
更多推荐




所有评论(0)