发表于 2024.07.16

• 此类寻找满足某种条件中的最小值的题目，通常可以使用二分搜索来解决。对于本题，我们定义check函数为判断是否满足条件(即遍历数组，累加每个元素的除法取上界结果)的函数，然后使用二分搜索来寻找最小的满足check函数为True的值。

  class Solution:
      def smallestDivisor(self, nums: List[int], threshold: int) -> int:
          def check(cand: int) -> bool:
              return sum((num + cand - 1) // cand for num in nums) <= threshold
  
          left, right = 1, max(nums)
          while left <= right:
              mid = (left + right) // 2
              if check(mid):
                  right = mid - 1
              else:
                  left = mid + 1
          return left

  优化：在check函数内累加除法结果时，如果累加值已经超过了threshold，则可以直接返回False，这样可以减少一些不必要的计算。

  class Solution:
      def smallestDivisor(self, nums: List[int], threshold: int) -> int:
          def check(cand: int) -> bool:
              res = 0
              for num in nums:
                  res += (num + cand - 1) // cand
                  if res > threshold:
                      break
              return res <= threshold
  
          left, right = 1, max(nums)
          while left <= right:
              mid = (left + right) // 2
              if check(mid):
                  right = mid - 1
              else:
                  left = mid + 1
          return left

• LC 题目链接