给定一个整数数组nums
和一个整数threshold
,我们将选择一个正整数除数并将所有数组除以它,并将除法的结果相加。找到最小除数,使得上述结果小于或等于threshold
。
除法的每个结果都四舍五入到大于或等于该元素的最接近的整数。(例如:7/3 = 3 和 10/2 = 5)。
保证会有答案。
示例 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).
示例 2:
Input: nums = [2,3,5,7,11], threshold = 11
Output: 3
示例 3:
Input: nums = [19], threshold = 5
Output: 4
约束:
1 <= nums.length <= 5 * 10^4
1 <= nums[i] <= 10^6
nums.length <= threshold <= 10^6
给定一个除求和募捐的值,求一个募捐这个中小数的商人和以慈善事业的价值。
因为值域固定,可以用二分法夹出答案。
class Solution {
public int smallestDivisor(int[] nums, int threshold) {
int left = 1, right = 1000000;
while (left < right) {
int mid = (right - left) / 2 + left;
int sum = 0;
for (int num : nums) {
sum += Math.ceil(1.0 * num / mid);
}
if (sum <= threshold) {
right = mid;
} else {
left = mid + 1;
}
}
return right;
}
}
联系客服