🚂 准时到达的列车最小时速

📝 题目描述

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

​ 每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。例如，第1趟列车需要1.5小时，那你必须再等待0.5小时，搭乘第2小时发车的第2趟列车。

​ 返回能满足你准时到达办公室所要求全部列车的最小正整数时速（单位：千米每小时），如果无法准时到达，则返回-1。

​ 本题生成的测试用例答案不超过 ${10}^7$，且hour的小数点后最多存在两位数字。

📋 代码模板

java

class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {

    }
}

typescript

function minSpeedOnTime(dist: number[], hour: number): number {
    
}

💡 提示

1. $n=dist.length$
2. $1\le n\le {10}^5$
3. $1\le dist[i]\le {10}^5$
4. $1\le hour\le {10}^9$
5. $hour$ 中，小数点后最多存在两位数字

🚀 示例

🖊️ 题解

​ 当所需时间 $hour$ 向上取整后依然小于 $dist.length$，那么无论速度多快，也不可能准时到达，可直接返回 $-1$。相反，若 $\lceil hour\rceil \ge dist.length$，只要速度够快，必定能够准时到达。

​ 设 $speed$ 为列车时速，随着 $speed$ 不断增大，乘坐每趟列车所需要的小时数单调递减，乘坐所有趟列车所需要的小时数 $requiredHour$ 也单调递减，其中 $requiredHour$ 的计算公式如下。

$$requiredHour=\sum _{i=0}^{n-2}\lceil \frac{dist[i]}{speed}\rceil +\frac{dist[n-1]}{speed},n=dist.length$$

​ 根据上述单调性，我们可以使用二分查找算法，找出满足条件 $requiredHour\le hour$ 的最小时速 $answer$。因为只要得到 $answer$，以下两个条件都是必然成立的。

$$\sum _{i=0}^{n-2}\lceil \frac{dist[i]}{low}\rceil +\frac{dist[n-1]}{low}>hour,low<answer$$$$\sum _{i=0}^{n-2}\lceil \frac{dist[i]}{high}\rceil +\frac{dist[n-1]}{high}\le hour,high>answer$$

​ 二分查找的下限可以设置为 $1$，这是因为 $1$ 为最小的正整数，即最小时速。而二分查找的上限可以设置为题目中告知的 ${10}^7$。

​ 综上所述，在区间 $[1,{10}^7]$ 中，使用二分查找，得到第一个使得条件 $requiredHour\le hour$ 成立的元素，即为最小时速 $answer$​​​。其中，$requiredHour\le hour$ 也是二分查找中 $check$ 函数为真的条件。

---

​ 需要说明的是，在二分查找的 $check$ 函数逻辑中，为了避免浮点数计算造成的潜在误差，我们可以将所有涉及计算的数都转化为整数，再进行条件比较。假设乘坐前 $n-1$ 趟列车所需要的时间为 $t$，那么如果能够准时到达终点，以下条件必定成立。

$$t+\frac{dist[n-1]}{speed}\le hour$$

​ 首先，考虑不等式左边，$t$ 为整数，但 $\frac{dist[n-1]}{mid}$ 为分数，因此我们可以在不等式的两边同时乘以 $mid$ 来消除分母。

$$t\cdot speed+dist[n-1]\le hour\cdot speed$$

​ 其次，考虑不等式右边，$mid$ 为整数，但 $hour$ 为两位小数，因此我们可以在不等式的两边同时乘以 $100$ 来消除小数，为了简单起见，我们可以引入 $hr=100\ast hour$​。

$$100(t\cdot speed+dist[n-1])\le hr\cdot speed$$

java

class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {
        int n = dist.length;
        if (n > Math.ceil(hour)) {
            return -1;
        }
        long hr = Math.round(hour * 100);
        int low = 1, high = (int) 1e7;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (check(dist, hr, mid)) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    private boolean check(int[] dist, long hr, int speed) {
        int n = dist.length;
        long requiredHour = 0;
        for (int i = 0; i < n - 1; i++) {
            requiredHour += (dist[i] + speed - 1) / speed;
        }
        requiredHour = 100 * (requiredHour * speed + dist[n - 1]);
        return requiredHour <= hr * speed;
    }
}

typescript

function minSpeedOnTime(dist: number[], hour: number): number {
    const n = dist.length;
    if (n > Math.ceil(hour)) {
        return - 1;
    }
    const hr = Math.round(hour * 100);
    const check = (speed: number): boolean => {
        let requiredHour = 0;
        for (let i = 0; i < n - 1; i++) {
            requiredHour += Math.ceil(dist[i] / speed);
        }
        requiredHour = 100 * (requiredHour * speed + dist[n - 1]);
        return requiredHour <= hr * speed;
    }
    let low = 1, high = 1e7;
    while (low <= high) {
        const mid = low + Math.floor((high - low) / 2);
        if (check(mid)) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

💭 复杂度分析

​ 基于二分查找的解决方案的复杂度分析如下。

• 时间复杂度：$O(n\log C)$，其中 $C$ 为二分查找的上下限之差，$n$ 为数组长度。
• 空间复杂度：$O(1)$。