【Leetcode Daily】1011在D天内送达包裹的能力

题目浅析

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

思路分享

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

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

• 参考题解

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        # 先要定好二分答案的左右区间起始,注意这是开区间
        left, right = max(weights)-1, 500*len(weights)+1

        def check(weights: List[int], ship_load: int, days: int) -> bool:
            # 此处把负载过小的情况快速地排除，加速
            if sum(weights) > ship_load*days:
                return False
            
            sum_num = 0
            use_days = 0
            for i in weights:
                sum_num += i
                if sum_num > ship_load:
                    sum_num = i
                    use_days += 1
            
            use_days += 1 if sum_num > 0 else 0

            return use_days <= days
        
        while left+1 < right:
            mid = (left + right) // 2
            if check(weights, mid, days):
                right = mid
            else:
                left = mid
        
        return right