JZX轻语：简

LeetCode 1011 - 在D天内送达包裹的能力

发表于2024年06月04日

#二分法

此类求解满足条件的最小值的题目，且满足小于该值时均不满足条件，大于该值时均满足条件，可考虑使用二分法来解决。首先确定二分的上下界[货物最大值, 货物总量](小于货物最大值必然不满足条件, 大于货物总量必然满足条件)，然后使用二分法来逼近满足条件的最小值。

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def check(cap: int) -> bool:
            required_days = 0
            cur_load = 0
            for weight in weights:
                if cur_load + weight > cap:
                    cur_load = 0
                    required_days += 1

                cur_load += weight
            return required_days + 1 <= days

        max_weight = sum_weight = max(weights), sum(weights)
        # 二分搜索找到最小满足条件的cap
        lo, hi = max_weight, sum_weight
        while lo <= hi:
            mid = (lo + hi) >> 1
            if check(mid):
                hi = mid - 1
            else:
                lo = mid + 1
        return lo

闪念标签：LC

题目链接：https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/