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. 函数minDamage的定义：

   • 输入：一个整数 power，两个整数数组 damage 和 health。两个数组的长度都是 n，表示 Bob 要面对的 n 个敌人的伤害和生命值。

2. 计算敌人的攻击周期：

   • 创建一个结构体 pair，包含两个字段 k 和 d，其中 k 表示消灭该敌人所需的秒数，d 表示该敌人每秒造成的伤害。
   • 用变量 a 存储每个敌人的这些信息。具体地，对于每个敌人 i，计算：
     • k = (health[i] - 1) / power + 1，这代表了需要几秒钟才能消灭敌人 i。
     • 将 k 和 damage[i] 作为一对存入数组 a。

3. 排序敌人：

   • 使用 slices.SortFunc 对敌人按照 k * damage 的值进行排序。排序的依据是：
     • 优先消灭对 Bob 造成伤害较大的敌人，因为在较长的存活时间内，伤害累积会更高。
   • 这可以确保那些可以造成最大累积伤害的敌人优先被攻击。

4. 计算总伤害：

   • 初始化一个变量 s 为0，表示活着的敌人总计的攻击周期。
   • 遍历排序后的敌人数组 a，对于每一个敌人 p：
     • 将当前敌人 p 的攻击周期 p.k 加到 s 上。
     • 计算 Bob 在消灭敌人 p 期间所遭受的伤害并累加到 ans：
       • 当前伤害贡献为 s * p.d，表示在消灭当前敌人期间，Bob 遭受的总伤害。
   • 最终，ans 就是 Bob 在消灭所有敌人之前所受到的最小总伤害。

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-*-

def min_damage(power, damage, health):
    class Pair:
        def __init__(self, k, d):
            self.k = k
            self.d = d
    
    a = []
    for h, d in zip(health, damage):
        k = (h - 1) // power + 1
        a.append(Pair(k, d))
    
    # 自定义排序函数
    def compare(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)