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.计算敌人的攻击周期：

• • 创建一个结构体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-*- 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)

我们相信 Go 语言和算法为普通开发者提供了强有力的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的 Go 语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。 欢迎关注“福大大架构师每日一题”，让 Go 语言和算法助力您的职业发展