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

🟢   🔖  贪心 数组  🔗 力扣 LeetCode

题目

You are entering a competition, and are given two positive integers initialEnergy and initialExperience denoting your initial energy and initial experience respectively.

You are also given two 0-indexed integer arrays energy and experience, both of length n.

You will face n opponents in order. The energy and experience of the ith opponent is denoted by energy[i] and experience[i] respectively. When you face an opponent, you need to have both strictly greater experience and energy to defeat them and move to the next opponent if available.

Defeating the ith opponent increases your experience by experience[i], but decreases your energy by energy[i].

Before starting the competition, you can train for some number of hours. After each hour of training, you can either choose to increase your initial experience by one, or increase your initial energy by one.

Return the minimum number of training hours required to defeat all nopponents.

Example 1:

Input: initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]

Output: 8

Explanation: You can increase your energy to 11 after 6 hours of training, and your experience to 5 after 2 hours of training.

You face the opponents in the following order:

• You have more energy and experience than the 0th opponent so you win.

  Your energy becomes 11 - 1 = 10, and your experience becomes 5 + 2 = 7.

• You have more energy and experience than the 1st opponent so you win.

  Your energy becomes 10 - 4 = 6, and your experience becomes 7 + 6 = 13.

• You have more energy and experience than the 2nd opponent so you win.

  Your energy becomes 6 - 3 = 3, and your experience becomes 13 + 3 = 16.

• You have more energy and experience than the 3rd opponent so you win.

  Your energy becomes 3 - 2 = 1, and your experience becomes 16 + 1 = 17.

You did a total of 6 + 2 = 8 hours of training before the competition, so we return 8.

It can be proven that no smaller answer exists.

Example 2:

Input: initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3]

Output: 0

Explanation: You do not need any additional energy or experience to win the competition, so we return 0.

Constraints:

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

题目大意

你正在参加一场比赛，给你两个 正 整数 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 。

在比赛前进行了 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. 对每个敌人，英雄的经验值必须严格大于敌人的经验值。

为了最小化训练时间，我们需要分别计算能量需求和经验需求。

1. 计算能量需求

英雄需要的总能量应大于所有敌人能量之和 totalEnergy，即满足以下条件： initialEnergy + addEnergy > totalEnergy

从而： addEnergy = max(0, totalEnergy + 1 - initialEnergy)

• 利用 reduce 方法快速计算 totalEnergy。
• 使用公式计算出需要补充的能量 addEnergy。

2. 计算经验需求

对于每个敌人，英雄的当前经验值 initialExperience 必须严格大于敌人的经验值： initialExperience > enemyExperience

否则，需要训练补充到至少 enemyExperience + 1，并在战斗后更新英雄的经验值。

计算过程：

• 遍历 experience 数组，逐个检查敌人的经验值。
• 如果 initialExperience <= enemyExperience：
  • 计算需要补充的经验值为 enemyExperience - initialExperience + 1。
  • 将补充值累加到 addExperience。
  • 更新英雄的经验值为 enemyExperience + 1。
• 无论是否补充，战斗后英雄的经验值都会增加当前敌人的经验值：initialExperience += enemyExperience。

最终，addExperience 记录了训练所需的总经验补充量。

3. 计算总训练时间

将能量和经验的补充时间相加： Total Training Time = addEnergy + addExperience

复杂度分析

• 时间复杂度：O(n)，计算总能量需要遍历 energy，计算经验需求需要遍历 experience，两个数组的长度都为 n。
• 空间复杂度：O(1)，只使用了常数级别的变量。

代码

/**
 * @param {number} initialEnergy
 * @param {number} initialExperience
 * @param {number[]} energy
 * @param {number[]} experience
 * @return {number}
 */
var minNumberOfHours = function (
	initialEnergy,
	initialExperience,
	energy,
	experience
) {
	// 计算需要补充的能量
	const totalEnergy = energy.reduce((a, b) => a + b, 0);
	const addEnergy = Math.max(0, totalEnergy + 1 - initialEnergy);

	// 计算需要补充的经验
	let addExperience = 0;
	for (let num of experience) {
		if (initialExperience <= num) {
			addExperience += num - initialExperience + 1; // 补充到比敌人多 1
			initialExperience = num + 1; // 更新经验值
		}
		initialExperience += num; // 战斗后获得经验
	}

	// 返回总训练时间
	return addEnergy + addExperience;
};