【LeetCode】2187. 完成旅途的最少时间
1. 题意
2. 分析
二分法有一个关键特征：如果答案answer满足题意，那么对于任何整数i，如果有i>=answer，那么i也会是一个存在的解，只不过不是最优解。
本题想要找出一个达到 totalTrips 趟需要的最少时间成本t，那么对于题目来说任何大于t的数也会是解，但不是最优解；任何小于t的数都不是解。这样整个值域就被分成了两部分，区间[0,t) 和 [t, +∞)，如下图所示：
那么使用二分法不断的折中找出这个边界值即可。
3. 代码
class Solution:def minimumTime(self, time: List[int], totalTrips: int) -> int:left = 1max_time = time[0]for cur_time in time:max_time = max(max_time, cur_time)# 如果由这辆最慢的车完成totalTrips 需要的时间right = max_time * totalTripswhile(left <= right):mid = (left+right)//2if self.check(mid, totalTrips, time):right = mid-1else:left = mid+1return left# time_cost 需要花费的最少时间# times 时间数组def check(self, time_cost, totalTrips, times):cnt = 0for time in times:cnt += (time_cost//time) # 当前这个time可以完成几趟return cnt >= totalTrips