2187.minimum-time-to-complete-trips.md

算法思路

关注数据量，

• 1 <= time.length <= 105
• 1 <= time[i], totalTrips <= 107

应该用 nlog(n) 的解法

随时间增加，能完成的旅途数量，具有单调性，考虑二分解法

首先得出 最长时间 = totalTrips * min(time)

然后用二分求解，得到 完成 至少 totalTrips 趟旅途需要花费的 最少 时间；

代码实现

class Solution {

    public long minimumTime(int[] time, int totalTrips) {
        Arrays.sort(time);
        long l = time[0], r = (long) totalTrips * time[0]; // 注意：int 转化 long 溢出问题
        while (l < r) {
            long mid = l + r >> 1;
            if (check(mid, time, totalTrips)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

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

}