这道题的核心是贪心 + 排序,难点在于推导出正确的排序规则。

💡 核心思路

· 策略一:集中攻击:选定一个敌人后,应连续攻击直至将其消灭。切换目标只会让已受攻击的敌人存活更久,造成更多伤害。
· 策略二:确定最优顺序:假设有两个敌人 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 语言的实现能帮助你解决问题。

 

Logo

Agent 垂直技术社区,欢迎活跃、内容共建。

更多推荐