2187. 完成旅途的最少时间

链接

思路

问题抽象，当选择时刻（t）等于1的话，那么只需要遍历t / time[i]得到每一个time公交车完成的旅途数。

换句话来说就是计算t / time[i]的总和是不是大于等于totalTrips。因为随着t不断增大，整体的综合也会不断增大，有单调性。

使用二分答案进行求解

1. 当我们的mid / time[i] >= totalTrips为true，说明mid是在右区间的，所以需要进行缩小。r = mid

2. 当我们的mid / time[i] <= totalTrips为false，说明mid是在左区间。l = mid + 1

需要注意一下二分的数据范围，r的范围应该是totalTrips*time中最小的数。

代码

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

        long min = Long.MAX_VALUE;
        for (int i : time) {
            min = Math.min(min, i);
        }

        long l = 1;
        long r = totalTrips * min;

        while (l < r) {
            long mid = (l + r) >> 1;
            if (get(time, mid) >= totalTrips) r = mid;
            else l = mid + 1;
        }

        return l;
    }

    public static long get(int[] t, long mid) {
        long res = 0;
        for (int i : t) {
            res += mid / i;
        }
        return res;
    }
}