Question

1883. 准时抵达会议现场的最小跳过休息次数

English Version

题目描述

给你一个整数 hoursBefore ，表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场，你必须途经 n 条道路。道路的长度用一个长度为 n 的整数数组 dist 表示，其中 dist[i] 表示第 i 条道路的长度（单位：千米）。另给你一个整数 speed ，表示你在道路上前进的速度（单位：千米每小时）。

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

• 例如，如果你通过一条道路用去 1.4 小时，那你必须停下来等待，到 2 小时才可以继续通过下一条道路。如果通过一条道路恰好用去 2 小时，就无需等待，可以直接继续。

然而，为了能准时到达，你可以选择 跳过 一些路的休息时间，这意味着你不必等待下一个整数小时。注意，这意味着与不跳过任何休息时间相比，你可能在不同时刻到达接下来的道路。

• 例如，假设通过第 1 条道路用去 1.4 小时，且通过第 2 条道路用去 0.6 小时。跳过第 1 条道路的休息时间意味着你将会在恰好 2 小时完成通过第 2 条道路，且你能够立即开始通过第 3 条道路。

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

 

示例 1：

输入：dist = [1,3,2], speed = 4, hoursBefore = 2
输出：1
解释：
不跳过任何休息时间，你将用 (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 小时才能抵达会议现场。
可以跳过第 1 次休息时间，共用 ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 小时抵达会议现场。
注意，第 2 次休息时间缩短为 0 ，由于跳过第 1 次休息时间，你是在整数小时处完成通过第 2 条道路。

示例 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 小时才能抵达会议现场。
可以跳过第 1 次和第 3 次休息时间，共用 ((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] <= 105
• 1 <= speed <= 106
• 1 <= hoursBefore <= 107

解法

方法一：动态规划

我们定义 $f[i][j]$ 表示考虑前 $i$ 条道路，恰好跳过 $j$ 次休息时间的最短用时。初始时 $f[0][0]=0$，其余 $f[i][j]=\infty$。

由于我们可以选择跳过或者不跳过第 $i$ 条道路的休息时间，因此我们可以列出状态转移方程：

$$ f[i][j]=\min\left{\begin{aligned} \lceil f[i-1][j]+\frac{d_i}{s}\rceil & \text{不跳过第 $i$ 条道路的休息时间} \ f[i-1][j-1]+\frac{d_i}{s} & \text{跳过第 $i$ 条道路的休息时间} \end{aligned}\right. $$

其中 $\lceil x\rceil$ 表示将 $x$ 向上取整。需要注意的是，由于我们需要保证恰好跳过 $j$ 次休息时间，因此我们必须有 $j\le i$；另外，如果 $j=0$，不能跳过任何休息时间。

由于浮点数运算以及向上取整运算可能会带来精度误差，因此我们引入一个常量 $eps = 10^{-8}$ 表示一个极小的正实数，在浮点数取整前先减去 $eps$，最后在比较 $f[n][j]$ 和 $hoursBefore$ 时，需要加上 $eps$。

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。其中 $n$ 是道路的数量。

class Solution:
  def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
    n = len(dist)
    f = [[inf] * (n + 1) for _ in range(n + 1)]
    f[0][0] = 0
    eps = 1e-8
    for i, x in enumerate(dist, 1):
      for j in range(i + 1):
        if j < i:
          f[i][j] = min(f[i][j], ceil(f[i - 1][j] + x / speed - eps))
        if j:
          f[i][j] = min(f[i][j], f[i - 1][j - 1] + x / speed)
    for j in range(n + 1):
      if f[n][j] <= hoursBefore + eps:
        return j
    return -1

class Solution {
  public int minSkips(int[] dist, int speed, int hoursBefore) {
    int n = dist.length;
    double[][] f = new double[n + 1][n + 1];
    for (int i = 0; i <= n; i++) {
      Arrays.fill(f[i], 1e20);
    }
    f[0][0] = 0;
    double eps = 1e-8;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= i; ++j) {
        if (j < i) {
          f[i][j] = Math.min(
            f[i][j], Math.ceil(f[i - 1][j]) + 1.0 * dist[i - 1] / speed - eps);
        }
        if (j > 0) {
          f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1.0 * dist[i - 1] / speed);
        }
      }
    }
    for (int j = 0; j <= n; ++j) {
      if (f[n][j] <= hoursBefore + eps) {
        return j;
      }
    }
    return -1;
  }
}

class Solution {
public:
  int minSkips(vector<int>& dist, int speed, int hoursBefore) {
    int n = dist.size();
    vector<vector<double>> f(n + 1, vector<double>(n + 1, 1e20));
    f[0][0] = 0;
    double eps = 1e-8;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= i; ++j) {
        if (j < i) {
          f[i][j] = min(f[i][j], ceil(f[i - 1][j] + dist[i - 1] * 1.0 / speed - eps));
        }
        if (j) {
          f[i][j] = min(f[i][j], f[i - 1][j - 1] + dist[i - 1] * 1.0 / speed);
        }
      }
    }
    for (int j = 0; j <= n; ++j) {
      if (f[n][j] <= hoursBefore + eps) {
        return j;
      }
    }
    return -1;
  }
};

func minSkips(dist []int, speed int, hoursBefore int) int {
  n := len(dist)
  f := make([][]float64, n+1)
  for i := range f {
    f[i] = make([]float64, n+1)
    for j := range f[i] {
      f[i][j] = 1e20
    }
  }
  f[0][0] = 0
  eps := 1e-8
  for i := 1; i <= n; i++ {
    for j := 0; j <= i; j++ {
      if j < i {
        f[i][j] = math.Min(f[i][j], math.Ceil(f[i-1][j]+float64(dist[i-1])/float64(speed)-eps))
      }
      if j > 0 {
        f[i][j] = math.Min(f[i][j], f[i-1][j-1]+float64(dist[i-1])/float64(speed))
      }
    }
  }
  for j := 0; j <= n; j++ {
    if f[n][j] <= float64(hoursBefore) {
      return j
    }
  }
  return -1
}

function minSkips(dist: number[], speed: number, hoursBefore: number): number {
  const n = dist.length;
  const f = Array.from({ length: n + 1 }, () => Array.from({ length: n + 1 }, () => Infinity));
  f[0][0] = 0;
  const eps = 1e-8;
  for (let i = 1; i <= n; ++i) {
    for (let j = 0; j <= i; ++j) {
      if (j < i) {
        f[i][j] = Math.min(f[i][j], Math.ceil(f[i - 1][j] + dist[i - 1] / speed - eps));
      }
      if (j) {
        f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + dist[i - 1] / speed);
      }
    }
  }
  for (let j = 0; j <= n; ++j) {
    if (f[n][j] <= hoursBefore + eps) {
      return j;
    }
  }
  return -1;
}

方法二

class Solution:
  def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
    n = len(dist)
    f = [[inf] * (n + 1) for _ in range(n + 1)]
    f[0][0] = 0
    for i, x in enumerate(dist, 1):
      for j in range(i + 1):
        if j < i:
          f[i][j] = min(f[i][j], ((f[i - 1][j] + x - 1) // speed + 1) * speed)
        if j:
          f[i][j] = min(f[i][j], f[i - 1][j - 1] + x)
    for j in range(n + 1):
      if f[n][j] <= hoursBefore * speed:
        return j
    return -1