Hard

题目描述

给你一个整数 hoursBefore，表示你要前往会议现场的可用小时数。为了到达会议现场，你需要途经 n 条道路。道路长度用一个长度为 n 的整数数组 dist 表示，其中 dist[i] 表示第 i 条道路的长度（单位：千米）。另给你一个整数 speed，表示你在道路上前进的速度（单位：千米/小时）。

当你通过第 i 条道路后，如果不是最后一条道路，你必须停下来休息并等待，直到 下一个整数小时 才能开始通过下一条道路。注意，你不需要在通过最后一条道路后休息，因为那时你已经到达会议现场了。

  • 例如，如果通过一条道路花费 1.4 小时，那么你必须等到第 2 小时才能通过下一条道路。如果通过一条道路恰好花费 2 小时，那么你不需要等待。

但是，为了能够准时到达，你可以选择 跳过 一些休息时间，这意味着你不需要等待下一个整数小时。注意，这意味着你可能会在不同的时刻到达后续的道路。

  • 例如，假设通过第一条道路花费 1.4 小时，通过第二条道路花费 0.6 小时。跳过第一条道路后的休息时间，你将恰好在第 2 小时到达第二条道路，让你立即开始通过第三条道路。

返回准时到达会议现场所需的 最小跳过次数，如果无法准时到达，则返回 -1 。

示例 1：

输入：dist = [1,3,2], speed = 4, hoursBefore = 2
输出：1
解释：
不跳过任何休息时间，你将到达时间为 (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 小时。
你可以跳过第一次休息时间，到达时间为 ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 小时。
注意，第二次休息时间缩短了，因为第三段路程是从整数小时开始的。

示例 2：

输入：dist = [7,3,5,5], speed = 2, hoursBefore = 10
输出：2
解释：
不跳过任何休息时间，你将到达时间为 (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 小时。
你可以跳过第一次和第三次休息时间，到达时间为 ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 小时。

示例 3：

输入：dist = [7,3,5,5], speed = 1, hoursBefore = 10
输出：-1
解释：即使跳过所有的休息时间，也无法准时到达会议现场。

提示：

  • n == dist.length
  • 1 <= n <= 1000
  • 1 <= dist[i] <= 10^5
  • 1 <= speed <= 10^6
  • 1 <= hoursBefore <= 10^7

解题思路

这是一个典型的动态规划问题。我们需要考虑在每条道路后是否跳过休息时间，以最小化总跳过次数的同时满足时间约束。

思路分析：

  1. 定义状态：dp[i][j] 表示前 i 条道路恰好跳过 j 次休息时间后的累计时间。
  2. 状态转移：对于第 i 条道路，我们有两种选择：
    • 不跳过休息：需要等到下一个整数小时，时间为 ceil(dp[i-1][j] + dist[i]/speed)
    • 跳过休息：直接累加时间，dp[i-1][j-1] + dist[i]/speed
  3. 边界条件：dp[0][0] = 0，其他状态初始化为无穷大。
  4. 最终答案：寻找最小的 j，使得 dp[n-1][j] <= hoursBefore。

关键优化：

  • 为避免浮点数精度问题，我们将所有时间乘以 speed，这样就可以用整数运算。
  • ceil(a/b) 可以用 (a + b - 1) / b 来计算（整数除法）。
  • 最多只需要跳过 n-1 次（除了最后一条路，每条路最多跳过一次）。

这个算法的核心是通过动态规划记录每种跳过次数下的最小时间，然后找到满足时间限制的最小跳过次数。

推荐解法： 整数化动态规划，避免浮点数运算带来的精度问题。

代码实现

class Solution {
public:
    int minSkips(vector<int>& dist, int speed, int hoursBefore) {
        int n = dist.size();
        long long limit = (long long)hoursBefore * speed;
        
        // dp[i][j] represents minimum time to finish first i roads with j skips
        vector<vector<long long>> dp(n + 1, vector<long long>(n, LLONG_MAX));
        dp[0][0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i && j < n; j++) {
                // Option 1: Don't skip rest after road i-1
                if (i == n) {
                    // Last road, no rest needed
                    if (dp[i-1][j] != LLONG_MAX) {
                        dp[i][j] = min(dp[i][j], dp[i-1][j] + dist[i-1]);
                    }
                } else {
                    // Not last road, need to wait for next integer hour
                    if (dp[i-1][j] != LLONG_MAX) {
                        long long time = dp[i-1][j] + dist[i-1];
                        // Ceiling division: (time + speed - 1) / speed * speed
                        long long nextHour = ((time + speed - 1) / speed) * speed;
                        dp[i][j] = min(dp[i][j], nextHour);
                    }
                }
                
                // Option 2: Skip rest after road i-1 (only if j > 0 and not last road)
                if (j > 0 && i < n && dp[i-1][j-1] != LLONG_MAX) {
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1] + dist[i-1]);
                }
            }
        }
        
        for (int j = 0; j < n; j++) {
            if (dp[n][j] <= limit) {
                return j;
            }
        }
        
        return -1;
    }
};

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        n = len(dist)
        limit = hoursBefore * speed
        
        # dp[i][j] represents minimum time to finish first i roads with j skips
        dp = [[float('inf')] * n for _ in range(n + 1)]
        dp[0][0] = 0
        
        for i in range(1, n + 1):
            for j in range(min(i, n)):
                # Option 1: Don't skip rest after road i-1
                if i == n:
                    # Last road, no rest needed
                    if dp[i-1][j] != float('inf'):
                        dp[i][j] = min(dp[i][j], dp[i-1][j] + dist[i-1])
                else:
                    # Not last road, need to wait for next integer hour
                    if dp[i-1][j] != float('inf'):
                        time = dp[i-1][j] + dist[i-1]
                        # Ceiling division
                        next_hour = ((time + speed - 1) // speed) * speed
                        dp[i][j] = min(dp[i][j], next_hour)
                
                # Option 2: Skip rest after road i-1 (only if j > 0 and not last road)
                if j > 0 and i < n and dp[i-1][j-1] != float('inf'):
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1] + dist[i-1])
        
        for j in range(n):
            if dp[n][j] <= limit:
                return j
        
        return -1

public class Solution {
    public int MinSkips(int[] dist, int speed, int hoursBefore) {
        int n = dist.Length;
        long limit = (long)hoursBefore * speed;
        
        // dp[i][j] represents minimum time to finish first i roads with j skips
        long[,] dp = new long[n + 1, n];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = long.MaxValue;
            }
        }
        dp[0, 0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < Math.Min(i, n); j++) {
                // Option 1: Don't skip rest after road i-1
                if (i == n) {
                    // Last road, no rest needed
                    if (dp[i-1, j] != long.MaxValue) {
                        dp[i, j] = Math.Min(dp[i, j], dp[i-1, j] + dist[i-1]);
                    }
                } else {
                    // Not last road, need to wait for next integer hour
                    if (dp[i-1, j] != long.MaxValue) {
                        long time = dp[i-1, j] + dist[i-1];
                        // Ceiling division
                        long nextHour = ((time + speed - 1) / speed) * speed;
                        dp[i, j] = Math.Min(dp[i, j], nextHour);
                    }
                }
                
                // Option 2: Skip rest after road i-1 (only if j > 0 and not last road)
                if (j > 0 && i < n && dp[i-1, j-1] != long.MaxValue) {
                    dp[i, j] = Math.Min(dp[i, j], dp[i-1, j-1] + dist[i-1]);
                }
            }
        }
        
        for (int j = 0; j < n; j++) {
            if (dp[n, j] <= limit) {
                return j;
            }
        }
        
        return -1;
    }
}

var minSkips = function(dist, speed, hoursBefore) {
    const n = dist.length;
    const eps = 1e-9;
    
    // dp[i][j] = minimum time to reach road i with j skips
    const dp = Array(n + 1).fill().map(() => Array(n + 1).fill(Infinity));
    dp[0][0] = 0;
    
    for (let i = 0; i < n; i++) {
        const travelTime = dist[i] / speed;
        
        for (let j = 0; j <= i; j++) {
            if (dp[i][j] === Infinity) continue;
            
            // Don't skip rest (except for last road)
            if (i < n - 1) {
                const timeWithRest = Math.ceil(dp[i][j] + travelTime - eps);
                dp[i + 1][j] = Math.min(dp[i + 1][j], timeWithRest);
            } else {
                // Last road, no rest needed
                dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + travelTime);
            }
            
            // Skip rest (if not last road and can skip)
            if (i < n - 1 && j < n - 1) {
                const timeWithoutRest = dp[i][j] + travelTime;
                dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], timeWithoutRest);
            }
        }
    }
    
    for (let j = 0; j <= n; j++) {
        if (dp[n][j] <= hoursBefore + eps) {
            return j;
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²) - 两层循环，外层遍历道路数，内层遍历跳过次数
空间复杂度O(n²) - 需要 dp 数组存储所有状态

相关题目