🚌 完成旅途的最少时间

📝 题目描述

​ 给你一个数组time，其中time[i]表示第i辆公交车完成一趟旅途所需要花费的时间。

​ 每辆公交车可以连续完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以立马开始下一趟旅途。每辆公交车独立运行，也就是说可以同时有多辆公交车在运行且互不影响。

​ 给你一个正整数totalTrips，表示所有公交车总共需要完成的旅途数目。请你返回完成至少totalTrips趟旅途需要花费的最少时间。

📋 代码模版

java

class Solution {
    public long minimumTime(int[] time, int totalTrips) {

    }
}

typescript

function minimumTime(time: number[], totalTrips: number): number {

}

💡 提示

1. $1\le time.length\le {10}^5$
2. $1\le time[i]\le {10}^7$
3. $1\le totalTrips\le {10}^7$

🚀 示例

🖊️ 题解

​ 设 $t$ 为花费的时间，随着 $t$ 不断增大，每辆公交车能完成的旅途趟数 $\lfloor \frac{t}{time[i]}\rfloor$单调递增，所有公交车完成的旅途趟数 $trips$ 也单调递增，其中 $trips$ 的计算公式如下 。

$$trips=\sum _{i=0}^{n-1}\lfloor \frac{t}{time[i]}\rfloor ,n=time.length$$

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

$$\sum _{i=0}^{n-1}\lfloor \frac{low}{time[i]}\rfloor <totalTrips,low<answer$$$$\sum _{i=0}^{n-1}\lfloor \frac{high}{time[i]}\rfloor \ge totalTrips,high>answer$$

​ 二分查找的下限可以设置为 $time$ 数组中的最小值 $minT$，这是因为当花费时间为 $minT$ 时，完成的旅途趟数是最小的（不能为 $0$）。而二分查找的上限可以设置为 $time$ 数组中的最小值与总趟数的乘积，即 $minT\cdot totalTrips$，这是因为答案不可能超过让最快的车跑 $totalTrips$ 趟所花费的时间。

​ 综上所述，在区间 $[minT,minT\cdot totalTrips]$ 中，使用二分查找，得到第一个使得条件 $trips\ge totalTrips$ 成立的元素，即为最小花费时间 $answer$​。其中，$trips\ge totalTrips$ 也是二分查找中 $check$ 函数为真的条件。

​ 为了进一步提高算法效率，我们还可以对 $check$ 函数进行优化，具体做法为：在统计能够完成的旅游趟数 $trips$ 时，若它的值已经达到了 $totalTrips$，可直接中断统计，并返回 $true$。

java

class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long minT = time[0];
        for (int tm : time) {
            minT = Math.min(tm, minT);
        }
        long low = minT, high = minT * totalTrips;
        while (low <= high) {
            long mid = low + ((high - low) >> 1);
            if (check(time, totalTrips, mid)) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    private boolean check(int[] time, int totalTrips, long t) {
        int trips = 0;
        for (int i = 0; i < time.length && trips < totalTrips; i++) {
            trips += t / time[i];
        }
        return trips >= totalTrips;
    }
}

typescript

function minimumTime(time: number[], totalTrips: number): number {
    const check = (t: number): boolean => {
        let trips = 0;
        for (let i = 0; i < time.length && trips < totalTrips; i++) {
            trips += Math.floor(t / time[i]);
        }
        return trips >= totalTrips;
    }
    const minT = Math.min(...time);
    let low = minT, high = minT * totalTrips;
    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)$。