完成比赛的最少时间
难度:
标签:
题目描述
You are given a 0-indexed 2D integer array tires where tires[i] = [fi, ri] indicates that the ith tire can finish its xth successive lap in fi * ri(x-1) seconds.
- For example, if
fi = 3andri = 2, then the tire would finish its1stlap in3seconds, its2ndlap in3 * 2 = 6seconds, its3rdlap in3 * 22 = 12seconds, etc.
You are also given an integer changeTime and an integer numLaps.
The race consists of numLaps laps and you may start the race with any tire. You have an unlimited supply of each tire and after every lap, you may change to any given tire (including the current tire type) if you wait changeTime seconds.
Return the minimum time to finish the race.
Example 1:
Input: tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4 Output: 21 Explanation: Lap 1: Start with tire 0 and finish the lap in 2 seconds. Lap 2: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds. Lap 3: Change tires to a new tire 0 for 5 seconds and then finish the lap in another 2 seconds. Lap 4: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds. Total time = 2 + 6 + 5 + 2 + 6 = 21 seconds. The minimum time to complete the race is 21 seconds.
Example 2:
Input: tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5 Output: 25 Explanation: Lap 1: Start with tire 1 and finish the lap in 2 seconds. Lap 2: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds. Lap 3: Change tires to a new tire 1 for 6 seconds and then finish the lap in another 2 seconds. Lap 4: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds. Lap 5: Change tires to tire 0 for 6 seconds then finish the lap in another 1 second. Total time = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 seconds. The minimum time to complete the race is 25 seconds.
Constraints:
1 <= tires.length <= 105tires[i].length == 21 <= fi, changeTime <= 1052 <= ri <= 1051 <= numLaps <= 1000
代码结果
运行时间: 618 ms, 内存: 44.6 MB
/*
* 思路：
* 1. 我们需要计算使用每种轮胎完成一定圈数的最少时间，包括换轮胎的时间。
* 2. 使用动态规划的方式，dp[i]表示完成i圈的最少时间。
* 3. 对于每个轮胎，预先计算在一定圈数下的累计时间（包括换轮胎的时间），并更新dp数组。
* 4. 返回dp[numLaps]作为结果。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class RaceTimeCalculator {
public int minTime(int[][] tires, int changeTime, int numLaps) {
int[] dp = new int[numLaps + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int[] tire : tires) {
int f = tire[0];
int r = tire[1];
int time = f;
for (int laps = 1; laps <= numLaps && time <= changeTime + f; laps++) {
int finalTime = time;
IntStream.rangeClosed(1, numLaps).map(i -> numLaps - i).filter(j -> j >= laps).forEach(j -> dp[j] = Math.min(dp[j], dp[j - laps] + finalTime));
time = time * r;
}
}
IntStream.rangeClosed(1, numLaps).forEach(laps -> {
IntStream.rangeClosed(1, laps).forEach(i -> dp[laps] = Math.min(dp[laps], dp[laps - i] + changeTime + dp[i]));
});
return dp[numLaps];
}
}
解释
方法:
这是一道动态规划问题，涉及到决策每一圈使用哪种轮胎以及何时换轮胎。首先，计算使用每种轮胎在连续使用时的最小耗时，并仅考虑在耗时变得不划算时停止（即耗时超过换新轮胎的时间）。使用一个数组 min_costs 来记录每种轮胎连续使用不同圈数时的最小耗时。然后，使用另一个动态规划数组 f[i] 来记录完成 i 圈的最小总耗时。对于每一圈，都试图找出使用之前计算的 min_costs 连续使用几圈轮胎并结合换轮胎的策略，来得到最小耗时。这样，通过组合之前的结果和当前的选择，动态地更新 f 数组，最终在 f[numLaps] 中得到完成比赛的最少时间。
时间复杂度:
O(t + numLaps)
空间复杂度:
O(numLaps)
代码细节讲解
🦆
在题解中提到的`min_costs`数组是如何初始化和更新的？请详细解释其作用和如何根据不同轮胎类型来更新这个数组。
▷🦆
在题解的动态规划部分，为什么初始条件`f[0]`被设置为`-changeTime`？这样的设置有什么特殊的用意或好处？
▷🦆
题解提到最多考虑连续使用18圈的情况，这个数字18是如何确定的？是否有可能存在更优的选择？
▷