2226. 每个小孩最多能分到多少糖果

题目

给你一个 下标从 0 开始 的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的 子堆 ，但 无法 再将两堆合并到一起。

另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到 相同 数量的糖果。每个小孩可以拿走 至多一堆 糖果，有些糖果可能会不被分配。

返回每个小孩可以拿走的 最大糖果数目 。

示例 1：

输入：candies = [5,8,6], k = 3
输出：5
解释：可以将 candies[1] 分成大小分别为 5 和 3 的两堆，然后把 candies[2] 分成大小分别为 5 和 1 的两堆。现在就有五堆大小分别为 5、5、3、5 和 1 的糖果。可以把 3 堆大小为 5 的糖果分给 3 个小孩。可以证明无法让每个小孩得到超过 5 颗糖果。

示例 2：

输入：candies = [2,5], k = 11
输出：0
解释：总共有 11 个小孩，但只有 7 颗糖果，但如果要分配糖果的话，必须保证每个小孩至少能得到 1 颗糖果。因此，最后每个小孩都没有得到糖果，答案是 0 。

提示：

1 <= candies.length <= 10^5
1 <= candies[i] <= 10^7
1 <= k <= 10^12

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-candies-allocated-to-k-children
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

每个小孩可以拿走的最大糖果数目介于到#card=math&code=max%28candies%29&id=nwA06)之间，可以在这个范围内二分，看能否满足这个。

代码

class Solution {
    public int maximumCandies(int[] candies, long k) {
        int ans = 0;
        int left = 0;
        int right = Arrays.stream(candies).max().getAsInt();
        int n = candies.length;
        Arrays.sort(candies);
        while (left < right) {
            // 使用二分看分给每个孩子mid糖果能否满足
            int mid = left + (right - left + 1) / 2;
            // 这里使用了嵌套了一个二分，将candies排序后，找到第一个不小于mid的数，只需要统计不小于mid的数就好了
            int j = searchFirst(candies, mid);
            // 注意int溢出问题
            long cnt = 0;
            for (int i = j; i < n; i++) {
                cnt += (long) candies[i] / mid;
            }
            if (cnt < k) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
    // 查找有序数组nums中第一个不小于target的数，返回其下标
    int searchFirst(int[] nums, int target) {
        int len = nums.length;
        int low = 0;
        int high = len - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}