Leetcode2383. 赢得比赛需要的最少训练时长

Every day a Leetcode

题目来源：2383. 赢得比赛需要的最少训练时长

解法1：模拟

可以分开考虑在比赛开始前，需要最少增加的精力和经验数量。

每次遇到一个对手，当前精力值都需要严格大于当前对手，否则需要增加精力值。因此，在击败最后一个对手后，剩余的精力值至少要为 1。

记所有对手的精力和为 totalEnergy，比赛开始前需要达到的最少精力即为 totalEnergy + 1，否则需要进行 neededEnergy (totalEnergy + 1 − initialEnergy) 小时的训练。

而对于经验，初始化当前经验值 currentExperience，可以遍历一次 experience 数组：

• 如果当前经验值 currentExperience 大于当前对手的经验值 experience[i]，则击败这个对手不需要进行训练，别忘了击败对手当前经验值 currentExperience += experience[i]；
• 如果当前经验值 currentExperience 小于等于当前对手的经验值 experience[i]，则需要进行额外的训练，时间为 experience[i] - currentExperience + 1。currentExperience 需要加上这个差值以及该对手的经验值。

遍历完数组之后可以得到增加经验方面需要进行的额外小时数 neededExperience。

neededEnergy + neededExperience 即为最终答案。

代码：

/** @lc app=leetcode.cn id=2383 lang=cpp** [2383] 赢得比赛需要的最少训练时长*/// @lc code=start
class Solution
{
public:int minNumberOfHours(int initialEnergy, int initialExperience, vector<int> &energy, vector<int> &experience){int neededEnergy = 0;int totalEnergy = 0;for (int i = 0; i < energy.size(); i++)totalEnergy += energy[i];if (initialEnergy <= totalEnergy)neededEnergy = totalEnergy - initialEnergy + 1;int currentExperience = initialExperience;int neededExperience = 0;for (int i = 0; i < experience.size(); i++){if (currentExperience <= experience[i]){int diff = experience[i] - currentExperience + 1;currentExperience += diff;neededExperience += diff;currentExperience += experience[i];}elsecurrentExperience += experience[i];}return neededEnergy + neededExperience;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(n)，其中 n 是数组 energy 和 experience 的长度。我们需要遍历 energy 和 experience 数组各一遍。

空间复杂度：O(1)。仅使用常数空间。