題目：

給你一個數組?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;}
}

性能：