完成比赛的最少时间

标签: 数组 动态规划

难度: Hard

给你一个下标从 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

Submission

运行时间: 618 ms

内存: 44.6 MB

class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:

        min_costs = [inf] * 18
        for f , r in tires:
            x , time , s = 1 , f , 0
            while time < changeTime + f:
                s += time
                min_costs[x] = min(min_costs[x],s)
                time *= r
                x += 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],changeTime + min_costs[j] + f[i-j])
        return f[numLaps]

Explain

这是一道动态规划问题，涉及到决策每一圈使用哪种轮胎以及何时换轮胎。首先，计算使用每种轮胎在连续使用时的最小耗时，并仅考虑在耗时变得不划算时停止（即耗时超过换新轮胎的时间）。使用一个数组 min_costs 来记录每种轮胎连续使用不同圈数时的最小耗时。然后，使用另一个动态规划数组 f[i] 来记录完成 i 圈的最小总耗时。对于每一圈，都试图找出使用之前计算的 min_costs 连续使用几圈轮胎并结合换轮胎的策略，来得到最小耗时。这样，通过组合之前的结果和当前的选择，动态地更新 f 数组，最终在 f[numLaps] 中得到完成比赛的最少时间。

时间复杂度: O(t + numLaps)

空间复杂度: O(numLaps)

class Solution:
    def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:

        min_costs = [inf] * 18  # 初始化每种连续使用圈数的最小耗时
        for f , r in tires:
            x , time , s = 1 , f , 0
            while time < changeTime + f:  # 当使用当前轮胎的耗时小于换轮胎的耗时时继续循环
                s += time
                min_costs[x] = min(min_costs[x],s)  # 更新最小耗时
                time *= r
                x += 1
        f = [inf] * (numLaps + 1)
        f[0] = -changeTime  # 初始化，第0圈不需要换轮胎耗时
        for i in range(1,numLaps+1):
            for j in range(1,min(18,i+1)):
                f[i] = min(f[i],changeTime + min_costs[j] + f[i-j])  # 动态规划更新完成 i 圈的最小耗时
        return f[numLaps]  # 返回完成所有圈的最小耗时

Explore

在题解中，`min_costs`数组用于存储每种轮胎连续使用不同圈数时的最小耗时。数组被初始化为无穷大（`inf`），这表示在开始时，没有任何耗时记录。对于每种轮胎，通过一个循环计算该轮胎连续使用1圈至多圈时的耗时。在循环中，每一圈的耗时是基于前一圈耗时乘以耗损率`r`计算得出的，累加到总耗时`s`上。如果轮胎使用的总耗时小于换新轮胎的耗时加上最初的单圈耗时，这个耗时就被视为有效，并更新到`min_costs`数组中。通过这种方式，`min_costs`数组为每种轮胎和每个可能的使用圈数提供了最优耗时数据。这个数据后续用于动态规划中，以确定在每一圈完成比赛时的最小耗时。

在题解中，`f[0]`被设置为`-changeTime`是为了抵消第一次换轮胎时加入的换轮胎耗时。因为完成0圈实际上不需要任何耗时，也不需更换轮胎。然而，在动态规划过程中，每次转换到新的圈数`i`时，算法都会假设可能包含一个换轮胎的动作，即在`f[i]`的计算中加入`changeTime`。为了保证从0圈到第1圈的计算正确（不应包含换轮胎的耗时），将`f[0]`初始化为`-changeTime`可以在计算第1圈时自动取消这个不必要的换轮胎耗时。

数字18是基于轮胎性能递减的速率以及换轮胎耗时的一个合理估计。这是一个经验值，用于限制在轮胎性能显著下降之前的最大使用圈数。理论上，如果轮胎的耗损率较低或换轮胎的耗时特别高，可能有更多圈数的情况下使用同一轮胎会更合算。因此，这个数字不是固定的，具体数值可以根据实际情况和具体轮胎的性能进行调整。在实际应用中，可以根据具体数据进行模拟或实验，找到最优的圈数限制。