LC 3273. 对 Bob 造成的最少伤害

https://leetcode.cn/problems/minimum-amount-of-damage-dealt-to-bob/description/

这题直觉上是贪心算法，但是怎么贪心是个问题，我是这么考虑的。假设每个敌人都需要使用 `R[i]` 轮才能消灭，而每个敌人造成的伤害是 `D[i]` ，我们只考虑最开始的时候，先选择 `R[0] or R[1]`

如果先选择 `R[0]` 的话，那么总体伤害是 $R [0] * (D [0] + D [1] + D [2] + . . .) + R [1] * (D [1] + D [2] + . . .) + F (R [2 :], D [2 :])$

如果先选择 `R[1]` 的话，那么总体伤害是 $R [1] * (D [0] + D [1] + D [2] + . . .) + R [0] * (D [1] + D [2] + . . .) + F (R [2 :], D [2 :])$

所以如果希望第一个伤害小的话，那么需要满足 $R [0] * D [1] < R [1] * D [0] => R [0] / D [0] < R [1] / D [1]$

所以排序的方式应该就是 $R / D$

class Solution:
    def minDamage(self, power: int, damage: List[int], health: List[int]) -> int:
        n = len(damage)
        idx = list(range(n))

        def f(x):
            r = (health[x] + power - 1) // power
            return r / damage[x]

        idx.sort(key=f)
        total = sum(damage)

        ans = 0
        for i in idx:
            r = (health[i] + power - 1) // power
            ans += r * total
            total -= damage[i]
        return ans