题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给出一个尽可能少的值，使得该值除 time 内各值之和为 totalTrips。

思路分享

  • 二分答案的基本思路可看【Leetcode Daily】1283使结果不超过阈值的最小除数。

  • 与参考题的思路基本相同，故就补充一点关于二分的要点，就是搞清楚更新中间点数值的大于和大于等于的区别，比如本题的大于等于，就会让 right 的地方保持为符合要求的下标。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        # 就是给出一个尽可能少的值，使得该值除 time 内各值之和为 totalTrips
        left, right = min(time)-1, min(time)*totalTrips
        while left+1 < right:
            mid = (left+right) // 2
            # print(f"mid:{mid}, left:{left}, right:{right}")
            if sum(mid // num for num in time) >= totalTrips:
                # print('r')
                right = mid
            else:
                # print('l')
                left = mid

        return right