题目描述

给你一个整数数组 nums 和一个正整数 threshold，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。

请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。

每个数除以除数后都向上取整，比方说 7/3 = 3，10/2 = 5。

题目保证一定有解。

样例

输入：nums = [1,2,5,9], threshold = 6
输出：5
解释：如果除数为 1 ，我们可以得到和为 17 （1+2+5+9）。
如果除数为 4 ，我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ，和为 5 (1+1+1+2)。

输入：nums = [2,3,5,7,11], threshold = 11
输出：3

输入：nums = [19], threshold = 5
输出：4

限制

• 1 <= nums.length <= 5 * 10^4
• 1 <= nums[i] <= 10^6
• nums.length <= threshold <= 10^6

算法

(二分答案) $O(n \log M)$

1. 由于 sum 与除数具有单调的关系，则我们可以通过二分除数，找到满足 threshold 最小的除数。
2. 如果求出的 sum 小于等于 threshold，则说明我们可以尝试继续调小除数；否则需要增大除数。

时间复杂度

• 最大的除数不超过 $10^6$，不低于 $1$，所以时间复杂度为 $O(n \log M)$，其中 $M=10^6$。

空间复杂度

• 只需要常数的额外空间。

C++ 代码

class Solution {
public:
    #define LL long long

    LL calc(int x, const vector<int> &num) {
        LL sum = 0;
        for (int t : num)
            sum += t / x + (bool)(t % x);
        return sum;
    }

    int smallestDivisor(vector<int>& nums, int threshold) {
        int l = 1, r = 1000000;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (calc(mid, nums) <= threshold)
                r = mid;
            else
                l = mid + 1;
        }

        return l;
    }
};