袋子里最少数目的球

给你一个数组 nums，允许你操作 k 次。

对于每一次操作，你可以将 nums 里面的元素 nums[i] 切割成两个正整数 a、b，并将切割后的正整数放入 nums 中。

他问你，你切割后得到的新数组的最大值最小为多少？

完善代码

class Solution {
public:
    int minimumSize(vector<int>& nums, int k) {

    }
};

样例说明

nums = [2,4,8,2]
k = 4

分割后的最小值为

nums = [2, 2, 2, 2, 2, 2, 2, 2]
res = 2

数据范围

\(1 \leq\) nums.size \(\leq 10 ^ 5\)

\(1 \leq\) k \(\leq 10 ^ 9\)

排序 + 二分查找

记为 l = 1；取 nums 数组中的最大值，记为 r。

答案一点介于 l 和 r 的区域之间，我们用二分查找；

定义中间游标为 mid = (l + r) / 2，如果将数组中的所有元素都切割成 mid 需要的操作数设为 t;

如果 t > k 说明 mid 太小了，切割次数不够用，此时让 l = mid + 1 ；

如果 t < k 说明 mid 太大了，还没用完切割次数，此时让 r = mid 查找左区间的形式。

时间复杂度为: \(O(nlog(n))\)

代码参考

class Solution {
public:
    typedef long long LL;
    LL get_tis(vector<int> &q, int a)
    {
        LL res = 0;
        for (auto x : q)
        {
            res += x / a + (x % a ? 0 : -1);
        }
        return res;
    }
    int minimumSize(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int l = 1, r = nums.back();
        int mid = (l + r) / 2;
        while (l < r)
        {
            LL t = get_tis(nums, mid);
            if (t > k) l = mid + 1;
            else r = mid;
            mid = (l + r) / 2;
        }
        return r;
    }
};