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

🟠   🔖  数组 二分查找  🔗 力扣 LeetCode

题目

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 take at most 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 <= 10^5
• 1 <= candies[i] <= 10^7
• 1 <= k <= 1012

题目大意

给你一个 下标从 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 <= 1012

解题思路

1. 确定搜索范围：

   • 最小值 left = 0（每个小孩可以拿 0 颗糖）。
   • 最大值 right = max(candies)（最优情况下，每个小孩最多可以拿到的糖果数）。

2. 二分 mid = (left + right + 1) / 2，表示尝试每个小孩拿 mid 颗糖，取上中位数，避免死循环：

   • 能否均分 mid 颗糖？
     • 计算 candies[i] 能分成多少份 Math.floor(candies[i] / mid)。
     • 累加所有堆的 totalCount，如果 totalCount ≥ k，说明可以分配 mid 颗糖。
   • 若能分配，则尝试更大的 mid，调整 left = mid。
   • 若不能分配，则尝试更小的 mid，调整 right = mid - 1。

3. 最终返回最大可行的 mid。

复杂度分析

• 时间复杂度：O(n log M)

  • 每次二分查找 O(log M)，其中 M = max(candies)。
  • 每次检查 O(n)，eachCanGet 遍历 candies 计算是否满足条件。
  • 总复杂度 O(n log M)。

• 空间复杂度：O(1)，仅使用常数个变量。

代码

/**
 * @param {number[]} candies
 * @param {number} k
 * @return {number}
 */
var maximumCandies = function (candies, k) {
	const eachCanGet = (n) => {
		let count = 0;
		for (const candy of candies) {
			count += (candy / n) | 0; // 用位运算代替 Math.floor
			if (count >= k) return true; // 提前终止，提高效率
		}
		return false;
	};
	let left = 0;
	let right = Math.max(...candies);
	while (left < right) {
		const mid = ((left + right + 1) / 2) | 0; // 取上中位数，避免死循环
		if (eachCanGet(mid)) {
			left = mid; // 保持可行解
		} else {
			right = mid - 1;
		}
	}
	return left;
};

相关题目

题号	标题	题解	标签	难度	力扣
875	爱吃香蕉的珂珂	[✓]	数组 二分查找	🟠	🀄️ 🔗
1760	袋子里最少数目的球	[✓]	数组 二分查找	🟠	🀄️ 🔗
1870	准时到达的列车最小时速		数组 二分查找	🟠	🀄️ 🔗
1898	可移除字符的最大数目		数组 双指针 字符串 1+	🟠	🀄️ 🔗
2064	分配给商店的最多商品的最小值	[✓]	数组 二分查找	🟠	🀄️ 🔗
2187	完成旅途的最少时间		数组 二分查找	🟠	🀄️ 🔗
2439	最小化数组中的最大值		贪心 数组 二分查找 2+	🟠	🀄️ 🔗
3075	幸福值最大化的选择方案		贪心 数组 排序	🟠	🀄️ 🔗