2188. 完成比赛的最少时间

发表于 分类于 阅读次数： Waline： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

  • 线性DP
  • 贪心
  • 完全背包

思路

一、问题抽象与核心难点

题目给定若干种轮胎，每种轮胎由两个参数描述：

  • \(f\)：该轮胎在新胎状态下跑第一圈的时间
  • \(r\)：每多跑一圈，单圈时间乘以的增长系数

若连续使用同一条轮胎跑圈，其第 \(k\) 圈耗时为： \[ f \cdot r^{k-1} \] 允许在任意两圈之间换胎，换胎需要固定时间 changeTime，且换胎后轮胎状态重置为新胎。

目标是：恰好跑完 numLaps 圈，使总时间最小。

1. 直接建模的失败尝试

一种直观但不可行的建模方式是： \[ dp[i][j][k] = \text{前 } i \text{ 圈，用第 } j \text{ 种轮胎，当前胎已连续跑 } k \text{ 圈的最小时间} \] 该状态维度过高，时间与空间复杂度均不可接受。

2. 关键建模思想：分段 + 状态压缩

比赛过程中，轮胎的历史使用情况不重要。 每次换胎，都相当于拿到一条“全新轮胎”，其第一圈耗时一定是 \(f\)。

因此，整个比赛可以被视为：

将 numLaps 圈划分为若干连续区间（段）， 每一段使用一条新轮胎连续跑若干圈。

二、子问题一：连续使用一条新胎跑 \(k\) 圈的最小时间

1. 子问题定义

定义数组： \[ \text{best}[k] = \min \left\{ \text{任意一种轮胎，连续使用 } k \text{ 圈的总时间} \right\} \] 对于某一轮胎 \((f, r)\)，连续跑 \(k\) 圈的耗时为： \[ f + fr + fr^2 + \cdots + fr^{k-1} \]

2. 有效枚举上界（剪枝理由）

随着 \(k\) 增大，单圈时间呈指数增长。 当出现： \[ f \cdot r^{k-1} > f + \text{changeTime} \] 说明：

  • 再跑这一圈，不如 换胎 + 跑新胎第一圈
  • 因此继续扩展该轮胎的连续圈数不可能出现在最优解中

由此，每条轮胎的有效连续圈数非常有限（通常几十以内）。

3. 预处理策略

对每一种轮胎：

  1. 从 \(k = 1\) 开始逐圈累加耗时
  2. 一旦单圈时间超过 \(f + \text{changeTime}\)，立即停止
  3. 用当前轮胎的连续耗时更新 best[k]

该步骤时间复杂度为： \[ O(\text{轮胎数} \times K) \] 其中 \(K\) 为连续圈数的自然上界，远小于 numLaps。

三、子问题二：分段动态规划

1. DP 状态定义

定义一维 DP： \[ dp[i] = \text{恰好跑完 } i \text{ 圈的最小总时间} \]

2. 状态转移方程

假设最后一段连续跑了 \(k\) 圈，则： \[ dp[i] = \min_{1 \le k \le i} \left( dp[i-k] + \text{best}[k] + \text{changeTime} \right) \] 解释：

  • best[k]：该段内连续跑 \(k\) 圈的最小耗时
  • changeTime：进入这一段前的换胎成本

3. 第一段的特殊处理

第一段不需要换胎。 实现上统一加上 changeTime，在最终答案中减去一次即可： \[ \text{answer} = dp[\text{numLaps}] - \text{changeTime} \]

4. 复杂度分析

  • DP 状态数：\(O(\text{numLaps})\)
  • 每个状态最多枚举 \(K\) 种段长

总时间复杂度： \[ O(\text{numLaps} \times K) \]

四、完整算法流程总结

  1. 预处理 best[k]
    • 枚举每种轮胎
    • 计算其可行的连续圈数及对应耗时
    • 更新全局最优
  2. 一维分段 DP
    • 使用 best 进行区间划分转移
    • 统一加换胎时间，最后减一次

五、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    // 快速幂：计算 x^k（用于 r^(j-1)）
    long long ksm(int x, int k) {
        long long res = 1, base = x;
        while (k) {
            if (k & 1) res *= base;
            base *= base;
            k >>= 1;
        }
        return res;
    }

    int minimumFinishTime(vector<vector<int>>& tires, int changeTime,
                          int numLaps) {

        // best[k]：连续使用一条新胎跑 k 圈的最小时间
        vector<long long> best;

        // 预处理每种轮胎的连续使用情况
        for (int i = 0; i < tires.size(); ++i) {
            int f = tires[i][0];
            int r = tires[i][1];
            long long sum = 0;

            for (int k = 1; k <= numLaps; ++k) {
                long long cur = (long long)f * ksm(r, k - 1);

                // 剪枝：继续跑不如换胎
                if (cur > f + changeTime) break;

                sum += cur;

                if ((int)best.size() < k)
                    best.push_back(sum);
                else
                    best[k - 1] = min(best[k - 1], sum);
            }
        }

        // dp[i]：恰好跑完 i 圈的最小时间
        static long long dp[100005];
        dp[0] = 0;

        for (int i = 1; i <= numLaps; ++i) {
            dp[i] = (long long)1e18;

            // 枚举最后一段的长度
            for (int k = 1; k <= min(i, (int)best.size()); ++k) {
                dp[i] = min(dp[i], dp[i - k] + best[k - 1] + changeTime);
            }
        }

        // 第一段不需要换胎，减去一次
        return dp[numLaps] - changeTime;
    }
};

六、建模思想一句话总结

本题的核心不是“轮胎跑到第几圈”， 而是“每次换胎后，连续跑多少圈最划算”。

通过将“轮胎选择 + 使用历史”压缩为“连续段长度”， 原本高维状态被成功降为 一维分段动态规划。