Easy

题目描述

你正在参加一个竞赛，给定两个正整数 initialEnergy 和 initialExperience 分别表示你的初始精力和初始经验值。

同时给定两个下标从 0 开始的整数数组 energy 和 experience，长度均为 n。

你将按顺序面对 n 个对手。第 i 个对手的精力和经验值分别用 energy[i] 和 experience[i] 表示。当你面对一个对手时，需要在精力和经验值上都严格超过对手才能击败对手并进入下一轮（如果有的话）。

击败第 i 个对手会使你的经验增加 experience[i]，但会使你的精力减少 energy[i]。

在开始比赛前，你可以训练若干小时。每小时的训练中，你可以选择将初始经验值增加 1，或将初始精力增加 1。

返回你击败所有 n 个对手所需的最少训练小时数。

示例 1：

输入：initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]
输出：8
解释：你可以在 6 小时的训练后将精力提高到 11，在 2 小时的训练后将经验提高到 5。
你按以下顺序面对对手：
- 你的精力和经验都比第 0 个对手更高，所以你赢了。
  你的精力变成 11 - 1 = 10，经验变成 5 + 2 = 7。
- 你的精力和经验都比第 1 个对手更高，所以你赢了。
  你的精力变成 10 - 4 = 6，经验变成 7 + 6 = 13。
- 你的精力和经验都比第 2 个对手更高，所以你赢了。
  你的精力变成 6 - 3 = 3，经验变成 13 + 3 = 16。
- 你的精力和经验都比第 3 个对手更高，所以你赢了。
  你的精力变成 3 - 2 = 1，经验变成 16 + 1 = 17。
你在比赛前总共训练了 6 + 2 = 8 小时，所以我们返回 8。
可以证明不存在更小的答案。

示例 2：

输入：initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3]
输出：0
解释：你不需要任何额外的精力或经验就能赢得比赛，所以我们返回 0。

提示：

  • n == energy.length == experience.length
  • 1 <= n <= 100
  • 1 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100

解题思路

这道题可以用贪心策略解决，关键思想是分别计算精力和经验的最少训练时长，然后求和。

解题思路：

  1. 精力计算：由于精力在每次战斗后都会减少，我们需要保证在整个过程中精力始终大于对手。最简单的方法是确保初始精力大于所有对手精力的总和，这样就能保证在任何时候都有足够的精力。

  2. 经验计算：经验在战斗后会增加，所以我们需要模拟整个战斗过程。对于每个对手，如果当前经验不够（小于等于对手经验），就需要训练来补充经验。

  3. 贪心策略：

    • 对于精力：计算所需的最少初始精力 = sum(energy) + 1，然后减去当前初始精力得到需要训练的时长
    • 对于经验：逐个模拟战斗过程，当经验不足时立即补充到刚好超过对手

这种方法是最优的，因为：

  • 精力的消耗是固定的，提前准备足够的精力是最经济的
  • 经验会随着战斗增加，所以按需补充是最经济的

算法流程：

  1. 计算精力训练时长：max(0, sum(energy) + 1 - initialEnergy)
  2. 模拟战斗过程计算经验训练时长
  3. 返回两者之和

代码实现

class Solution {
public:
    int minNumberOfHours(int initialEnergy, int initialExperience, vector<int>& energy, vector<int>& experience) {
        int energyTraining = 0, expTraining = 0;
        int currentExp = initialExperience;
        
        // 计算精力训练时长
        int totalEnergyNeeded = 0;
        for (int e : energy) {
            totalEnergyNeeded += e;
        }
        energyTraining = max(0, totalEnergyNeeded + 1 - initialEnergy);
        
        // 计算经验训练时长
        for (int i = 0; i < experience.size(); i++) {
            if (currentExp <= experience[i]) {
                int need = experience[i] + 1 - currentExp;
                expTraining += need;
                currentExp += need;
            }
            currentExp += experience[i];
        }
        
        return energyTraining + expTraining;
    }
};

class Solution:
    def minNumberOfHours(self, initialEnergy: int, initialExperience: int, energy: List[int], experience: List[int]) -> int:
        energy_training = 0
        exp_training = 0
        current_exp = initialExperience
        
        # 计算精力训练时长
        total_energy_needed = sum(energy)
        energy_training = max(0, total_energy_needed + 1 - initialEnergy)
        
        # 计算经验训练时长
        for exp in experience:
            if current_exp <= exp:
                need = exp + 1 - current_exp
                exp_training += need
                current_exp += need
            current_exp += exp
        
        return energy_training + exp_training

public class Solution {
    public int MinNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {
        int energyTraining = 0, expTraining = 0;
        int currentExp = initialExperience;
        
        // 计算精力训练时长
        int totalEnergyNeeded = 0;
        foreach (int e in energy) {
            totalEnergyNeeded += e;
        }
        energyTraining = Math.Max(0, totalEnergyNeeded + 1 - initialEnergy);
        
        // 计算经验训练时长
        for (int i = 0; i < experience.Length; i++) {
            if (currentExp <= experience[i]) {
                int need = experience[i] + 1 - currentExp;
                expTraining += need;
                currentExp += need;
            }
            currentExp += experience[i];
        }
        
        return energyTraining + expTraining;
    }
}

var minNumberOfHours = function(initialEnergy, initialExperience, energy, experience) {
    let energyTraining = 0, expTraining = 0;
    let currentExp = initialExperience;
    
    // 计算精力训练时长
    const totalEnergyNeeded = energy.reduce((sum, e) => sum + e, 0);
    energyTraining = Math.max(0, totalEnergyNeeded + 1 - initialEnergy);
    
    // 计算经验训练时长
    for (let i = 0; i < experience.length; i++) {
        if (currentExp <= experience[i]) {
            const need = experience[i] + 1 - currentExp;
            expTraining += need;
            currentExp += need;
        }
        currentExp += experience[i];
    }
    
    return energyTraining + expTraining;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历所有对手一次计算精力总和，再遍历一次模拟经验获取过程
空间复杂度O(1)只使用常数级别的额外空间存储变量