问题：
给定一个数组，求一个除数，
使得数组中每个元素被该数除后（有余数则结果+1）的和，不超过threshold。
(For example: 7/3 = 3 and 10/2 = 5).
Example 1: Input: nums = [1,2,5,9], threshold = 6 Output: 5 Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). Example 2: Input: nums = [2,3,5,7,11], threshold = 11 Output: 3 Example 3: Input: nums = [19], threshold = 5 Output: 4 Constraints: 1 <= nums.length <= 5 * 10^4 1 <= nums[i] <= 10^6 nums.length <= threshold <= 10^6
解法：二分查找(Binary Search)
最小值l：1
最大值r：max(nums)（由于nums.length <= threshold）
找到一个最小的m，使得 sum(n1/m, n2/m...nn/m) <= threshold
?? 注意：这里除方法的规则为：
可转换为：
给原数+（除数-1）后，再去做除法计算。
代码参考：
1 class Solution { 2 public: 3 int smallestDivisor(vector<int>& nums, int threshold) { 4 int l = 1, r = INT_MIN; 5 for(int n:nums) r=max(r, n); 6 while(l<r) { 7 int m = l+(r-l)/2; 8 int sum = 0; 9 for(int n:nums) { 10 sum+=((n+m-1)/m); 11 } 12 if(sum<=threshold) { 13 r = m; 14 } else { 15 l = m+1; 16 } 17 } 18 return l; 19 } 20 };
1283. Find the Smallest Divisor Given a Threshold
原文：https://www.cnblogs.com/habibah-chang/p/13496276.html