Hard

题目描述

给你一个整数 power 和两个整数数组 damage 和 health，两个数组的长度都是 n。

鲍勃有 n 个敌人，当敌人 i 还活着时（即 health[i] > 0），每秒会对鲍勃造成 damage[i] 点伤害。

每秒，在敌人对鲍勃造成伤害后，他会选择一个仍然活着的敌人，对其造成 power 点伤害。

确定在所有 n 个敌人都死亡之前，鲍勃将受到的最小总伤害点数。

示例 1：

输入：power = 4, damage = [1,2,3,4], health = [4,5,6,8]
输出：39
解释：
- 在前两秒攻击敌人 3，之后敌人 3 死亡，鲍勃受到的伤害是 10 + 10 = 20 点。
- 在接下来的两秒攻击敌人 2，之后敌人 2 死亡，鲍勃受到的伤害是 6 + 6 = 12 点。
- 在接下来的一秒攻击敌人 0，之后敌人 0 死亡，鲍勃受到的伤害是 3 点。
- 在接下来的两秒攻击敌人 1，之后敌人 1 死亡，鲍勃受到的伤害是 2 + 2 = 4 点。

示例 2：

输入：power = 1, damage = [1,1,1,1], health = [1,2,3,4]
输出：20

示例 3：

输入：power = 8, damage = [40], health = [59]
输出：320

提示：

  • 1 <= power <= 10^4
  • 1 <= n == damage.length == health.length <= 10^5
  • 1 <= damage[i], health[i] <= 10^4

解题思路

这是一个贪心算法问题。关键在于确定杀死敌人的最优顺序。

思路分析：

设敌人 i 需要 t_i = ceil(health[i] / power) 时间来杀死。当我们在敌人 i 和 j 之间选择时，需要比较两种杀死顺序的总伤害：

  1. 先杀 i 后杀 j：t_i * (damage[i] + damage[j]) + t_j * damage[j]
  2. 先杀 j 后杀 i：t_j * (damage[i] + damage[j]) + t_i * damage[i]

简化后可得：选择先杀 i 更优当且仅当 damage[i] * t_j > damage[j] * t_i。

这给出了贪心策略：按照 damage[i] / t_i 从大到小的顺序杀死敌人。直观上，我们应该优先杀死"单位时间伤害产出"最高的敌人。

算法步骤：

  1. 计算每个敌人的杀死时间 t_i = ceil(health[i] / power)
  2. 按照 damage[i] / t_i 降序排序敌人
  3. 按排序后的顺序依次杀死敌人，累计总伤害

这种贪心策略能保证全局最优解，因为任意两个相邻敌人的交换都不会产生更优解。

代码实现

class Solution {
public:
    long long minDamage(int power, vector<int>& damage, vector<int>& health) {
        int n = damage.size();
        vector<int> indices(n);
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        
        // 按照 damage[i] / time[i] 降序排序
        sort(indices.begin(), indices.end(), [&](int i, int j) {
            long long ti = (health[i] + power - 1) / power;
            long long tj = (health[j] + power - 1) / power;
            return (long long)damage[i] * tj > (long long)damage[j] * ti;
        });
        
        long long totalDamage = 0;
        long long currentDamagePerSecond = 0;
        for (int dmg : damage) {
            currentDamagePerSecond += dmg;
        }
        
        for (int idx : indices) {
            long long timeToKill = (health[idx] + power - 1) / power;
            totalDamage += currentDamagePerSecond * timeToKill;
            currentDamagePerSecond -= damage[idx];
        }
        
        return totalDamage;
    }
};

class Solution:
    def minDamage(self, power: int, damage: List[int], health: List[int]) -> int:
        n = len(damage)
        indices = list(range(n))
        
        # 按照 damage[i] / time[i] 降序排序
        def compare(i, j):
            ti = (health[i] + power - 1) // power
            tj = (health[j] + power - 1) // power
            return damage[j] * ti - damage[i] * tj
        
        indices.sort(key=cmp_to_key(compare))
        
        total_damage = 0
        current_damage_per_second = sum(damage)
        
        for idx in indices:
            time_to_kill = (health[idx] + power - 1) // power
            total_damage += current_damage_per_second * time_to_kill
            current_damage_per_second -= damage[idx]
        
        return total_damage

public class Solution {
    public long MinDamage(int power, int[] damage, int[] health) {
        int n = damage.Length;
        var indices = Enumerable.Range(0, n).ToArray();
        
        // 按照 damage[i] / time[i] 降序排序
        Array.Sort(indices, (i, j) => {
            long ti = (health[i] + power - 1) / power;
            long tj = (health[j] + power - 1) / power;
            return ((long)damage[j] * ti).CompareTo((long)damage[i] * tj);
        });
        
        long totalDamage = 0;
        long currentDamagePerSecond = damage.Sum(d => (long)d);
        
        foreach (int idx in indices) {
            long timeToKill = (health[idx] + power - 1) / power;
            totalDamage += currentDamagePerSecond * timeToKill;
            currentDamagePerSecond -= damage[idx];
        }
        
        return totalDamage;
    }
}

var minDamage = function(power, damage, health) {
    const n = damage.length;
    const indices = Array.from({length: n}, (_, i) => i);
    
    // 按照 damage[i] / time[i] 降序排序
    indices.sort((i, j) => {
        const ti = Math.ceil(health[i] / power);
        const tj = Math.ceil(health[j] / power);
        return damage[j] * ti - damage[i] * tj;
    });
    
    let totalDamage = 0;
    let currentDamagePerSecond = damage.reduce((sum, dmg) => sum + dmg, 0);
    
    for (const idx of indices) {
        const timeToKill = Math.ceil(health[idx] / power);
        totalDamage += currentDamagePerSecond * timeToKill;
        currentDamagePerSecond -= damage[idx];
    }
    
    return totalDamage;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n log n)
空间复杂度O(n)

其中 n 是敌人的数量。时间复杂度主要来自排序操作，空间复杂度来自存储敌人索引的数组。

相关题目