赢得比赛需要的最少训练时长
难度:
标签:
题目描述
代码结果
运行时间: 26 ms, 内存: 16.2 MB
/* 思路:
1. 使用stream计算累积的精力需求和经验需求。
2. 通过计算缺少的精力和经验来确定需要训练的时间。
*/
import java.util.stream.IntStream;
public class Solution {
public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {
int totalEnergy = IntStream.of(energy).sum();
int additionalEnergy = Math.max(0, totalEnergy + 1 - initialEnergy);
int additionalExperience = 0;
int currentExperience = initialExperience;
for (int exp : experience) {
if (currentExperience <= exp) {
additionalExperience += (exp - currentExperience + 1);
currentExperience = exp + 1;
}
currentExperience += exp;
}
return additionalEnergy + additionalExperience;
}
}
解释
方法:
本题解的核心思路是在比赛开始前计算击败所有对手所需的最小训练时间。解决步骤分为两部分:1. 确保精力足够。计算击败所有对手所需的总精力,与初始精力比较,如果不足,则计算所需额外精力。2. 确保经验足够。遍历每一个对手,检查当前经验是否足以击败对手。如果不够,计算所需的额外经验,并更新当前经验。最后,返回累计的额外精力和经验作为总训练时间。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
如何确定初始精力至少需要比所有对手的总精力多1点,这种策略是否最优化了精力的使用?
▷🦆
为什么在判断不足以击败对手时,更新当前经验为`exp * 2 + 1`,这样的计算方式是否有特定的理论依据或是如何得出的?
▷🦆
在计算所需额外经验时,`need_exp += exp - sum_exp + 1`的公式如何确保累计的经验正好足够而不过量?
▷