leetcode
leetcode 2051 ~ 2100
赢得比赛需要的最少训练时长

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

难度:

标签:

题目描述

代码结果

运行时间: 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点,这种策略是否最优化了精力的使用?
这种策略的目的是确保在每一轮比赛中都有足够的精力来应对对手,且在比赛结束后至少还剩余1点精力,这样可以避免比赛中因精力耗尽而失败。这是一种保守的策略,确保了在任何情况下都不会因为精力不足而输掉比赛。虽然这可能导致在某些情况下精力的使用略显多余(例如,如果能够确保每次都只用刚好足够的精力),但在没有更多信息的情况下,这种策略确保了安全和保障,可以视为一种最优策略,特别是在缺乏对对手行为的详细预测时。
🦆
为什么在判断不足以击败对手时,更新当前经验为`exp * 2 + 1`,这样的计算方式是否有特定的理论依据或是如何得出的?
当当前经验不足以击败对手时,更新经验为`exp * 2 + 1`是为了确保在下一次遭遇相同或更强的对手时可以直接击败对方。计算方式`exp * 2 + 1`来自于设想最坏情况下对手的经验可能与当前对手相同,因此需要有足够的经验不仅击败当前的对手,还要足够应对可能的更高经验值的对手。加1则是为了确保即使对手的经验与当前经验相同,也能保有优势。这种策略偏向于过度确保安全,从而减少在后续比赛中因经验不足再次进行额外训练的需要。
🦆
在计算所需额外经验时,`need_exp += exp - sum_exp + 1`的公式如何确保累计的经验正好足够而不过量?
该公式`need_exp += exp - sum_exp + 1`确保了每次遇到经验不足以击败对手的情况时,都精确计算出足以击败对手并略有余量的最小经验值。这里的`+1`是为了确保在经验值相等的情况下可以胜出,因此该公式计算出的是确切所需的最小额外经验。这种计算方式在保证胜利的同时避免了过量的经验累积,因为每次计算都是基于当前的累积经验和对手当前的经验需求。这样可以最大程度地减少不必要的经验训练,使训练时间和资源得到最优化利用。

相关问题