LeetCode 2187.完成旅途的最少时间

题目：

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

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

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

思路：

代码：

class Solution {public long minimumTime(int[] time, int totalTrips) {int minT = Integer.MAX_VALUE;for (int t : time) {minT = Math.min(minT, t);}long left = minT - 1; // 循环不变量：check(left) 恒为 falselong right = (long) minT * totalTrips; // 循环不变量：check(right) 恒为 truewhile (left + 1 < right) { // 开区间 (left, right) 不为空long mid = (left + right) >>> 1;if (check(mid, time, totalTrips)) {right = mid; // 缩小二分区间为 (left, mid)} else {left = mid; // 缩小二分区间为 (mid, right)}}// 此时 left 等于 right-1// check(left) = false 且 check(right) = true，所以答案是 rightreturn right; // 最小的 true}private boolean check(long x, int[] time, int totalTrips) {long sum = 0;for (int t : time) {sum += x / t;if (sum >= totalTrips) {return true;}}return false;}
}

性能：