【Leetcode Daily】1283使结果不超过阈值的最小除数

题目浅析

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

• 简单地说，就是给一个数组和一个阈值，现在找到一个尽可能大的数值 n，使得数组的每个值除 n 后之和小于阈值。

思路分享

• 二分的基本思路可看【Leetcode Daily】34在排序数组中查找元素的第一个和最后一个位置。

• 本题属于二分答案中的求最小系列，二分的思路是：既然求最小，那就是区间右侧满足条件，但左侧不满足，然后一点点逼近。

  https://leetcode.cn/problems/find-the-smallest-divisor-given-a-threshold/solutions/2989469/mo-ban-er-fen-da-an-qiu-zui-xiao-pythonj-ukwe/

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

• 参考题解

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

        return right