class Solution {
public:
long long minDamage(int power, vector<int>& damage, vector<int>& health) {
}
};
3273. 对 Bob 造成的最少伤害
给你一个整数 power 和两个整数数组 damage 和 health ，两个数组的长度都为 n 。
Bob 有 n 个敌人，如果第 i 个敌人还活着（也就是健康值 health[i] > 0 的时候），每秒钟会对 Bob 造成 damage[i] 点 伤害。
每一秒中，在敌人对 Bob 造成伤害 之后 ，Bob 会选择 一个 还活着的敌人进行攻击，该敌人的健康值减少 power 。
请你返回 Bob 将 所有 n 个敌人都消灭之前，最少 会收到多少伤害。
示例 1：
输入：power = 4, damage = [1,2,3,4], health = [4,5,6,8]
输出：39
解释：
10 + 10 = 20 点。6 + 6 = 12 点。3 点。2 + 2 = 4 点。示例 2：
输入：power = 1, damage = [1,1,1,1], health = [1,2,3,4]
输出：20
解释：
4 点。3 + 3 = 6 点。2 + 2 + 2 = 6 点。1 + 1 + 1 + 1 = 4 点。示例 3：
输入：power = 8, damage = [40], health = [59]
输出：320
提示：
1 <= power <= 1041 <= n == damage.length == health.length <= 1051 <= damage[i], health[i] <= 104原站题解
golang 解法, 执行用时: 153 ms, 内存消耗: 9.8 MB, 提交时间: 2024-09-18 16:50:52
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
}
python3 解法, 执行用时: 351 ms, 内存消耗: 39 MB, 提交时间: 2024-09-18 16:50:36
class Solution:
def minDamage(self, power: int, damage: List[int], health: List[int]) -> int:
a = [((h - 1) // power + 1, d) for h, d in zip(health, damage)]
a.sort(key=lambda p: p[0] / p[1])
# 另一种排序写法
# a.sort(key=cmp_to_key(lambda p, q: p[0] * q[1] - q[0] * p[1]))
ans = s = 0
for k, d in a:
s += k
ans += s * d
return ans
def minDamage2(self, power: int, damage: List[int], health: List[int]) -> int:
n = len(damage)
for i in range(n):
health[i] = (health[i] - 1) // power + 1
ans = s = 0
for i in sorted(range(n), key=lambda i: health[i] / damage[i]):
s += health[i]
ans += s * damage[i]
return ans