同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个下标从 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 <= 105
tires[i].length == 2
1 <= fi, changeTime <= 105
2 <= ri <= 105
1 <= numLaps <= 1000
我们注意到,连续使用同一个轮胎 $(f, r)$ 跑 $i$ 圈,那么第 $i$ 圈的耗时不应该超过 $changeTime + f$,否则我们可以在第 $i$ 圈的时候换轮胎,这样总耗时会更少。即:
$$ f \times r^{i-1} \leq changeTime + f $$
我们可以求出满足上式的最大的 $i$,要使得 $i$ 最大,那么 $f$ 和 $r$ 应该尽可能小,根据题目的数据范围,我们取 $f=1$, $r=2$,那么 $2^{i-1} \leq changeTime + 1$,即 $i \leq \log_2(changeTime + 1) + 1$。根据这个结论,以及题目中 $changeTime$ 的数据范围,我们可以知道 $i$ 最大为 $17$。
我们定义 $cost[i]$ 表示使用同一个轮胎跑 $i$ 圈的最小耗时,那么我们可以预处理出 $cost$ 数组,然后使用动态规划求解即可。定义 $f[i]$ 表示跑 $i$ 圈的最小耗时,那么我们可以得到状态转移方程:
$$ f[i] = (\min_{1 \leq j \leq \min(17, i)} f[i-j] + cost[j]) + changeTime $$
初始时 $f[0] = -changeTime$,最终答案为 $f[numLaps]$。
时间复杂度 $O((n + numLaps) \times \log T_{max})$,空间复杂度 $O(n + \log T_{max})$,其中 $T_{max}$ 是题目中 $f_i$, $r_i$ 和 $changeTime$ 的最大值。本题中 $\log T_{max} \approx 17$。
class Solution:
def minimumFinishTime(
self, tires: List[List[int]], changeTime: int, numLaps: int
) -> int:
cost = [inf] * 18
for f, r in tires:
i, s, t = 1, 0, f
while t <= changeTime + f:
s += t
cost[i] = min(cost[i], s)
t *= r
i += 1
f = [inf] * (numLaps + 1)
f[0] = -changeTime
for i in range(1, numLaps + 1):
for j in range(1, min(18, i + 1)):
f[i] = min(f[i], f[i - j] + cost[j])
f[i] += changeTime
return f[numLaps]
class Solution {
public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
final int inf = 1 << 30;
int[] cost = new int[18];
Arrays.fill(cost, inf);
for (int[] e : tires) {
int f = e[0], r = e[1];
int s = 0, t = f;
for (int i = 1; t <= changeTime + f; ++i) {
s += t;
cost[i] = Math.min(cost[i], s);
t *= r;
}
}
int[] f = new int[numLaps + 1];
Arrays.fill(f, inf);
f[0] = -changeTime;
for (int i = 1; i <= numLaps; ++i) {
for (int j = 1; j < Math.min(18, i + 1); ++j) {
f[i] = Math.min(f[i], f[i - j] + cost[j]);
}
f[i] += changeTime;
}
return f[numLaps];
}
}
class Solution {
public:
int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {
int cost[18];
memset(cost, 0x3f, sizeof(cost));
for (auto& e : tires) {
int f = e[0], r = e[1];
int s = 0;
long long t = f;
for (int i = 1; t <= changeTime + f; ++i) {
s += t;
cost[i] = min(cost[i], s);
t *= r;
}
}
int f[numLaps + 1];
memset(f, 0x3f, sizeof(f));
f[0] = -changeTime;
for (int i = 1; i <= numLaps; ++i) {
for (int j = 1; j < min(18, i + 1); ++j) {
f[i] = min(f[i], f[i - j] + cost[j]);
}
f[i] += changeTime;
}
return f[numLaps];
}
};
func minimumFinishTime(tires [][]int, changeTime int, numLaps int) int {
const inf = 1 << 30
cost := [18]int{}
for i := range cost {
cost[i] = inf
}
for _, e := range tires {
f, r := e[0], e[1]
s, t := 0, f
for i := 1; t <= changeTime+f; i++ {
s += t
cost[i] = min(cost[i], s)
t *= r
}
}
f := make([]int, numLaps+1)
for i := range f {
f[i] = inf
}
f[0] = -changeTime
for i := 1; i <= numLaps; i++ {
for j := 1; j < min(18, i+1); j++ {
f[i] = min(f[i], f[i-j]+cost[j])
}
f[i] += changeTime
}
return f[numLaps]
}
function minimumFinishTime(tires: number[][], changeTime: number, numLaps: number): number {
const cost: number[] = Array(18).fill(Infinity);
for (const [f, r] of tires) {
let s = 0;
let t = f;
for (let i = 1; t <= changeTime + f; ++i) {
s += t;
cost[i] = Math.min(cost[i], s);
t *= r;
}
}
const f: number[] = Array(numLaps + 1).fill(Infinity);
f[0] = -changeTime;
for (let i = 1; i <= numLaps; ++i) {
for (let j = 1; j < Math.min(18, i + 1); ++j) {
f[i] = Math.min(f[i], f[i - j] + cost[j]);
}
f[i] += changeTime;
}
return f[numLaps];
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。