leetcode1283

 1 class Solution:
 2     def smallestDivisor(self, nums: 'List[int]', threshold: int) -> int:
 3         n = len(nums)
 4         nums = sorted(nums)
 5         l,h = 1,nums[n-1]
 6         target = h
 7         while l <= h:
 8             mid = l + (h - l) // 2
 9             r = 0
10             for i in range(n):
11                 cur = nums[i]
12                 fix = 0#本题计算商的时候会向上进1，因此如果余数不为0，则商要+1
13                 if cur % mid != 0:
14                     fix += 1#余数不为0，商要+1
15                 r += cur // mid + fix
16             if r <= threshold:
17                 target = mid
18                 h = mid - 1
19             else:#r > threshold
20                 l = mid + 1
21         return target

算法思想：二分查找。

从1到nums中的最大值，作为左右边界。进行二分查找。

target默认为nums中的最大值，这样保证除数之和最小。(此时r=1 * n)

每次以mid作为除数计算目标值，并根据目标值与threshold的比较，进行二分查找。

注意第7行的判断条件是 l <= h。