发表于 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 题目链接