2025-04-07：对 Bob 造成的最少伤害。用go语言，给定一个整数 power 和两个整数数组 damage 和 hea

2025-04-07：对 Bob 造成的最少伤害。用go语言，给定一个整数 power 和两个整数数组 damage 和 health，这两个数组的长度相同，都为 n。

Bob 有 n 个敌人，当第 i 个敌人仍然存活时（即 health[i] > 0），每秒他会受到来自该敌人 damage[i] 点的伤害。在每秒钟结束时，Bob会选择一个还活着的敌人进行攻击，使该敌人的健康值减少 power。

请计算在 Bob 消灭所有敌人之前，他所受到的最小总伤害。

1 <= power <= 10000。

1 <= n == damage.length == health.length <= 100000。

1 <= damage[i], health[i] <= 10000。

输入：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 点。

题目来自leetcode3273。

大体步骤如下：

1. 1. 函数minDamage的定义：
   • • 输入：一个整数 power，两个整数数组 damage 和 health。两个数组的长度都是 n，表示 Bob 要面对的 n 个敌人的伤害和生命值。
2. 2. 计算敌人的攻击周期：
   • • 创建一个结构体 pair，包含两个字段 k 和 d，其中 k 表示消灭该敌人所需的秒数，d 表示该敌人每秒造成的伤害。
   • • 用变量 a 存储每个敌人的这些信息。具体地，对于每个敌人 i，计算：
     • • k = (health[i] - 1) / power + 1，这代表了需要几秒钟才能消灭敌人 i。
     • • 将 k 和 damage[i] 作为一对存入数组 a。
3. 3. 排序敌人：
   • • 使用 slices.SortFunc 对敌人按照 k * damage 的值进行排序。排序的依据是：
     • • 优先消灭对 Bob 造成伤害较大的敌人，因为在较长的存活时间内，伤害累积会更高。
   • • 这可以确保那些可以造成最大累积伤害的敌人优先被攻击。
4. 4. 计算总伤害：
   • • 初始化一个变量 s 为0，表示活着的敌人总计的攻击周期。
   • • 遍历排序后的敌人数组 a，对于每一个敌人 p：
     • • 将当前敌人 p 的攻击周期 p.k 加到 s 上。
     • • 计算 Bob 在消灭敌人 p 期间所遭受的伤害并累加到 ans：
       • • 当前伤害贡献为 s * p.d，表示在消灭当前敌人期间，Bob 遭受的总伤害。
   • • 最终，ans 就是 Bob 在消灭所有敌人之前所受到的最小总伤害。
5. 5. 输出结果：
   • • 打印结果，即 Bob 受到的最小总伤害。

时间复杂度

• • 计算每个敌人消灭所需的时间为 O(n)，而计算每个敌人的伤害为 O(n)。因此这部分的复杂度为 O(n)。
• • 排序的复杂度为 O(n log n)。
• • 综上所述，整体时间复杂度为 O(n log n)。

空间复杂度

• • 创建一个结构体数组 a，其大小与 health 和 damage 数组相同，为 O(n)。
• • 其他临时变量的空间开销相对较小，因此总体空间复杂度为 O(n)。

总结：该代码的时间复杂度是 O(n log n)，空间复杂度是 O(n)。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
)

func minDamage(power int, damage, health []int) (ans int64) {
    type pair struct{ k, d int }
    a := make([]pair, len(health))
    for i, h := range health {
        a[i] = pair{(h-1)/power + 1, damage[i]}
    }
    slices.SortFunc(a, func(p, q pair)int { return p.k*q.d - q.k*p.d })

    s := 0
    for _, p := range a {
        s += p.k
        ans += int64(s) * int64(p.d)
    }
    return
}

func main() {
    power := 4
    damage := []int{1, 2, 3, 4}
    health := []int{4, 5, 6, 8}
    result := minDamage(power, damage, health)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

defmin_damage(power, damage, health):
    classPair:
        def__init__(self, k, d):
            self.k = k
            self.d = d
    
    a = []
    for h, d inzip(health, damage):
        k = (h - 1) // power + 1
        a.append(Pair(k, d))
    
    # 自定义排序函数
    defcompare(p, q):
        return p.k * q.d - q.k * p.d
    
    # 在Python中，sorted函数不支持自定义比较函数，需要使用functools.cmp_to_key
    from functools import cmp_to_key
    a.sort(key=cmp_to_key(compare))
    
    ans = 0
    s = 0
    for p in a:
        s += p.k
        ans += s * p.d
    
    return ans

power = 4
damage = [1, 2, 3, 4]
health = [4, 5, 6, 8]
result = min_damage(power, damage, health)
print(result)