[LeetCode] 2226. Maximum Candies Allocated to K Children

You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can be allocated candies from only one pile of candies and some piles of candies may go unused.

Return the maximum number of candies each child can get.

Example 1:
Input: candies = [5,8,6], k = 3
Output: 5
Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.

Example 2:
Input: candies = [2,5], k = 11
Output: 0
Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.

Constraints:
1 <= candies.length <= 105
1 <= candies[i] <= 107
1 <= k <= 1012

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

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

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

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

思路

思路是二分，而且是在答案上二分。

题目只允许我们把一堆糖果分成多个更小的堆，所以最后每个小孩能拿走的糖果数最大是不会超过糖果堆中的最大值的。所以我们可以二分这个最大值，然后判断是否能够分配给k个小孩。

复杂度

时间O(nlogn)
空间O(1)

代码

Java实现

class Solution {
    public int maximumCandies(int[] candies, long k) {
        long sum = 0;
        int max = 0;
        for (int candy : candies) {
            max = Math.max(max, candy);
            sum += candy;
        }
        // corner case
        // 总糖果数都不够 k 个孩子分配至少 1 颗，直接返回 0
        if (sum < k) {
            return 0;
        }

        // normal case
        int left = 1;
        int right = max;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (helper(candies, mid, k)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    private boolean helper(int[] candies, long count, long k) {
        long res = 0;
        for (int candy : candies) {
            res += candy / count;
            if (res >= k) {
                break;
            }
        }
        return res >= k;
    }
}