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