准时到达的列车最小时速

题目链接 (opens new window)

难度：中等

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。

每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。

例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。 返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。

生成的测试用例保证答案不超过 107 ，且 hour 的 小数点后最多存在两位数字 。

示例 1：

输入：dist = [1,3,2], hour = 6
输出：1
解释：速度为 1 时：
- 第 1 趟列车运行需要 1/1 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。
- 由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。
- 你将会恰好在第 6 小时到达。
示例 2：

输入：dist = [1,3,2], hour = 2.7
输出：3
解释：速度为 3 时：
- 第 1 趟列车运行需要 1/3 = 0.33333 小时。
- 由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。
- 你将会在第 2.66667 小时到达。
示例 3：

输入：dist = [1,3,2], hour = 1.9
输出：-1
解释：不可能准时到达，因为第 3 趟列车最早是在第 2 小时发车。
 

提示：

n == dist.length
1 <= n <= 10^5
1 <= dist[i] <= 10^5
1 <= hour <= 10^9
hours 中，小数点后最多存在两位数字

我们都知道，速度等于路程除以时间，这道题给出了所有路程以及要求的时间，那么我们就可以求得所有列车的平均速度。

但这个速度并不是最终答案，因为列车是有多趟的，并且是整点才发车，即使列车的速度再快提前到了也不能立马换车，而是需要等待下一趟列车发车。

虽然这个速度不是我们要的答案，但是他也代表着按时到达可能的最小速度，如果每一趟列车都卡在整点到达那么是可以立马换乘的。

那如果我们每次尝试一个速度，判断是否可以按时到达，如果不行就把速度加一，直到找到一个可以按时到达的，就是答案要的最小速度。

在此之前需要先处理一下不能到达的情况，因为换乘的机制，每次至少要花费一个小时，那么如果时间小于等于列车的趟数-1的话，是无论如何都不能按时到达的。

还有最后一趟列车也是需要特殊处理的，因为不需要再换乘了，不用再等到整点。

function minSpeedOnTime(dist: number[], hour: number): number {
    const dis = dist.reduce((p, n) => p+n, 0) // 距离
    const v_avg = Math.ceil(dis / hour) // 平均速度
    const len = dist.length
    if (hour <= (len -1)) return -1
    let v = v_avg
    for(;;v++) {
      let t = 0, flag = true
      for(let i = 0; i < len - 1; i++) {
        t = Math.ceil(t + dist[i] / v)
        if (t >= hour) {
          flag = false
          break
        }
      }
      // 如果时间已经超过则提升速度
      if (!flag) continue
      // 最后一趟列车花费的时间
      t += dist[len - 1] / v
      if (t <= hour) {
        return v
      }
    }
};

虽然是暴力解法，结果也毫无悬念的超时了，但也可以为其他解法提供思路。

这个解法的问题是每次速度加一的提升速度太慢了，但即使每次加二加三面对庞大的数据量也是杯水车薪，而且每次加多少速度也不能确定。

这时就想到，如果我们知道速度的上限（一定可以按时到达的速度），有了一个区间，就可以用二分来寻找想要的速度了，并且查找的时间复杂度降低到O(lgn)。

那么如何确定速度的上限呢？我的想法是因为坐车+换乘最少也要花1小时，那么假定每一趟列车最多只需要花费1小时，则每一趟的速度都是不同的，取最大值就能保证所有列车都能在一小时内完成坐车+换乘。

此外，由于最后一趟车不需要换乘，需要额外计算最后一趟车的速度，例如最后一趟车距离有100米，但是时间只剩下0.1h了，那么最后一趟车的速度应该是100/0.1 = 1000m/h而不是100。

function minSpeedOnTime(dist: number[], hour: number): number {
  const len = dist.length
  let v_max = 0
  const dis = dist.reduce((p, n) => {
    v_max = Math.max(n, v_max)
    return p + n
  }, 0)
  const left_hour = hour - parseInt(String(hour))
  const d = dist[len - 1]
  v_max = Math.max(v_max, Math.ceil(d / left_hour))
  
  // 注意这里不能用ceil，因为精度问题可能整数后面带有小数，导致可能满足的最小速度加一了
  const v_avg = Math.floor(dis / hour)
  if (hour <= (len -1)) return -1
  let l = v_avg, r = v_max
  while (l < r) {
    const v_mid = Math.floor((l + r) / 2)
    if (isOnTime(v_mid, dist, hour)) {
      r = v_mid
    } else {
      l = v_mid + 1
    }
  }
  return l
};

const isOnTime = (v, dist, hour) => {
  let t = 0, flag = true, len = dist.length
  for(let i = 0; i < len - 1; i++) {
    t = Math.ceil(t + dist[i] / v)
    if (t >= hour) {
      return false
    }
  }
  t += dist[len - 1] / v
  if (t <= hour) {
    return true
  } else {
    return false
  }
}

拿下！一开始没考虑到最后一趟车的速度问题，想着最大速度取最长的路程/1即可，最后也是在错误样例中才发现的这个问题。

如果没有错误样例可能还要花更多的时间来发现这个问题。接下来看看官解吧。

function minSpeedOnTime(dist: number[], hour: number): number {
    const n = dist.length;
    // 将 hour 乘 100 以转为整数
    const hr = Math.round(hour * 100);
    // 时间必须要大于路程段数减 1
    if (hr <= (n - 1) * 100) {
        return -1;
    }
    // 二分
    let l = 1;
    let r = 10000000;
    while (l < r) {
        const mid = l + Math.floor((r - l) / 2);
        // 判断当前时速是否满足时限
        let t = 0;
        // 前 n-1 段中第 i 段贡献的时间： floor(dist[i] / mid)
        for (let i = 0; i < n - 1; ++i) {
            t += Math.floor((dist[i] - 1) / mid) + 1;
        }
        // 最后一段贡献的时间： dist[n-1] / mid
        t *= mid;
        t += dist[n - 1];
        if (t * 100 <= hr * mid) { // 通分以转化为整数比较
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l; // 满足条件的最小时速
};

官解也是二分，不过他直接把时间转化为整数，然后直接比较，省去了浮点数运算。并且把区间的左右都直接写死了，省去了确定区间上下限的过程。

虽然这是一种取巧的办法，但确实很不错，因为题目提示中，已经给出了路程的最大范围，也有说hours中，小数点后最多存在两位数字。那么可以求最后一趟车的速度，按照最大路程/最小时间可以得到最大速度，也就是10^5 / 0.01 = 10^7。

最低速度为1，这个没什么好说的。虽然这个区间特别大，但因为是二分查找，所以速度也不会差太多。

时间复杂度：O(nlog(C))，其中 n 为 dist 的长度，C 为二分的上下界之差。每一次二分都需要 O(n) 的时间计算花费的总时间。