二分查找寻找左边界-2187. 完成旅途的最少时间
2187. 完成旅途的最少时间
看到最少时间,又是单调的,就需要想到二分查找。
看这个题目的时间复杂度,on方必然会超出时间复杂度,随着次数的增加,时间一定也是增加的,当满足大于等t之后都是可以的,就是需要扎到二分查找的左边界。
public long minimumTime(int[] time, int totalTrips) {long l=1;long r=(long)Arrays.stream(time).max().getAsInt()*totalTrips;while (l<r){long mid= ((r-l)/2+l);if (check(mid, time,totalTrips)){//符合 找左边界r=mid;}else{l=mid+1;}}return l;}public static boolean check(long t,int [] time,int total){long cnt=0;for(int x:time){cnt+=t/x;}return cnt>=total;}