class Solution {
public:
int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {
}
};
2188. 完成比赛的最少时间
给你一个下标从 0 开始的二维整数数组 tires ，其中 tires[i] = [fi, ri] 表示第 i 种轮胎如果连续使用，第 x 圈需要耗时 fi * ri(x-1) 秒。
fi = 3 且 ri = 2 ，且一直使用这种类型的同一条轮胎，那么该轮胎完成第 1 圈赛道耗时 3 秒，完成第 2 圈耗时 3 * 2 = 6 秒，完成第 3 圈耗时 3 * 22 = 12 秒，依次类推。同时给你一个整数 changeTime 和一个整数 numLaps 。
比赛总共包含 numLaps 圈，你可以选择 任意 一种轮胎开始比赛。每一种轮胎都有 无数条 。每一圈后，你可以选择耗费 changeTime 秒 换成 任意一种轮胎（也可以换成当前种类的新轮胎）。
请你返回完成比赛需要耗费的 最少 时间。
示例 1：
输入：tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4 输出：21 解释： 第 1 圈：使用轮胎 0 ，耗时 2 秒。 第 2 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。 第 3 圈：耗费 5 秒换一条新的轮胎 0 ，然后耗时 2 秒完成这一圈。 第 4 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。 总耗时 = 2 + 6 + 5 + 2 + 6 = 21 秒。 完成比赛的最少时间为 21 秒。
示例 2：
输入：tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5 输出：25 解释： 第 1 圈：使用轮胎 1 ，耗时 2 秒。 第 2 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。 第 3 圈：耗时 6 秒换一条新的轮胎 1 ，然后耗时 2 秒完成这一圈。 第 4 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。 第 5 圈：耗时 6 秒换成轮胎 0 ，然后耗时 1 秒完成这一圈。 总耗时 = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 秒。 完成比赛的最少时间为 25 秒。
提示：
1 <= tires.length <= 105tires[i].length == 21 <= fi, changeTime <= 1052 <= ri <= 1051 <= numLaps <= 1000原站题解
golang 解法, 执行用时: 288 ms, 内存消耗: 25.1 MB, 提交时间: 2023-09-14 11:17:55
func minimumFinishTime(tires [][]int, changeTime, numLaps int) int {
minSec := [18]int{}
for i := range minSec {
minSec[i] = math.MaxInt32
}
for _, tire := range tires {
f, r := tire[0], tire[1]
for x, time, sum := 1, f, 0; time <= changeTime+f; x++ {
sum += time
minSec[x] = min(minSec[x], sum)
time *= r
}
}
f := make([]int, numLaps+1)
f[0] = -changeTime
for i := 1; i <= numLaps; i++ {
f[i] = math.MaxInt32
for j := 1; j <= 17 && j <= i; j++ {
f[i] = min(f[i], f[i-j]+minSec[j])
}
f[i] += changeTime
}
return f[numLaps]
}
func min(a, b int) int { if a > b { return b }; return a }
cpp 解法, 执行用时: 612 ms, 内存消耗: 174.9 MB, 提交时间: 2023-09-14 11:17:41
class Solution {
public:
int minimumFinishTime(vector<vector<int>> &tires, int changeTime, int numLaps) {
vector<int> minSec(18, INT_MAX / 2); // 除二是防止下面计算状态转移时溢出
for (auto &tire : tires) {
long time = tire[0];
for (int x = 1, sum = 0; time <= changeTime + tire[0]; ++x) {
sum += time;
minSec[x] = min(minSec[x], sum);
time *= tire[1];
}
}
vector<int> f(numLaps + 1, INT_MAX);
f[0] = -changeTime;
for (int i = 1; i <= numLaps; ++i) {
for (int j = 1; j <= min(17, i); ++j)
f[i] = min(f[i], f[i - j] + minSec[j]);
f[i] += changeTime;
}
return f[numLaps];
}
};
java 解法, 执行用时: 14 ms, 内存消耗: 99.5 MB, 提交时间: 2023-09-14 11:17:28
class Solution {
public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
var minSec = new int[18];
Arrays.fill(minSec, Integer.MAX_VALUE / 2); // 除二是防止下面计算状态转移时溢出
for (var tire : tires) {
long time = tire[0];
for (int x = 1, sum = 0; time <= changeTime + tire[0]; ++x) {
sum += time;
minSec[x] = Math.min(minSec[x], sum);
time *= tire[1];
}
}
var f = new int[numLaps + 1];
Arrays.fill(f, Integer.MAX_VALUE);
f[0] = -changeTime;
for (var i = 1; i <= numLaps; ++i) {
for (var j = 1; j <= Math.min(17, i); ++j)
f[i] = Math.min(f[i], f[i - j] + minSec[j]);
f[i] += changeTime;
}
return f[numLaps];
}
}
python3 解法, 执行用时: 996 ms, 内存消耗: 45.7 MB, 提交时间: 2023-09-14 11:17:11
class Solution:
def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
min_sec = [inf] * 18
for f, r in tires:
x, time, sum = 1, f, 0
while time <= changeTime + f:
sum += time
min_sec[x] = min(min_sec[x], sum)
time *= r
x += 1
f = [0] * (numLaps + 1)
f[0] = -changeTime
for i in range(1, numLaps + 1):
f[i] = changeTime + min(f[i - j] + min_sec[j] for j in range(1, min(18, i + 1)))
return f[numLaps]