What is the maximum number of candies each child can get in the 'Maximum Candies Allocated to K Children' problem?

The goal is to find the maximum number of candies that can be allocated to each child while ensuring that each child receives an equal number, using binary search to optimize the allocation.

How does binary search help in solving the 'Maximum Candies Allocated to K Children' problem?

Binary search allows us to efficiently narrow down the possible maximum number of candies by testing feasible solutions within a valid answer space.

What happens if there are fewer candies than children in the 'Maximum Candies Allocated to K Children' problem?

If there are fewer candies than children, the result will be 0 since it's impossible to allocate at least one candy to each child.

How do I determine if a certain number of candies can be allocated to k children?

For a candidate number of candies, iterate through the piles and count how many full allocations can be made. If the total number is greater than or equal to k, it's feasible.

What is the time complexity of the solution for the 'Maximum Candies Allocated to K Children' problem?

The time complexity is O(n log m), where n is the number of piles and m is the maximum number of candies in any pile.

#2226

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

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

给你一个下标从 0 开始的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的子堆，但无法再将两堆合并到一起。另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到相同数量的糖果。每个小孩可以拿走…

数组二分查找

题目描述

给你一个 下标从 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⁵
1 <= candies[i] <= 10⁷
1 <= k <= 10¹²

lightbulb

解题思路

方法一：二分查找

我们注意到，如果每个小孩能分到糖果数 $v$ ，那么对于任意 $v' \lt v$ ，每个小孩也能分到 $v'$ 颗糖果。因此，我们可以使用二分查找的方法找到最大的 $v$ ，使得每个小孩能分到 $v$ 颗糖果。

我们定义二分查找的左边界 $l = 0$ ，右边界 $r = \max(\text{candies})$ ，其中 $\max(\text{candies})$ 表示数组 $\text{candies}$ 中的最大值。在二分查找的过程中，我们每次取 $v$ 的中间值 $v = \left\lfloor \frac{l + r + 1}{2} \right\rfloor$ ，然后计算每个小孩能分到的糖果数 $v$ 的总和，如果总和大于等于 $k$ ，则说明每个小孩能分到 $v$ 颗糖果，此时我们更新左边界 $l = v$ ，否则我们更新右边界 $r = v - 1$ 。最终，当 $l = r$ 时，我们找到了最大的 $v$ 。

时间复杂度 $O(n \times \log M)$ ，其中 $n$ 表示数组 $\text{candies}$ 的长度，而 $M$ 表示数组 $\text{candies}$ 中的最大值。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        l, r = 0, max(candies)
        while l < r:
            mid = (l + r + 1) >> 1
            if sum(x // mid for x in candies) >= k:
                l = mid
            else:
                r = mid - 1
        return l

speed

复杂度分析

指标	值
时间	O(n \log m)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidate should be able to explain binary search principles and how they apply to this problem.
question_mark
Candidate must show an understanding of how to validate each candidate number of candies during the binary search.
question_mark
Candidate should demonstrate clarity in adjusting the binary search range based on feasibility checks.

warning

常见陷阱

外企场景

error
Confusing the binary search logic with linear search or brute force approaches.
error
Failing to correctly check if a certain number of candies can be allocated to all k children.
error
Not properly handling edge cases like not having enough candies to distribute to all children.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if there are fewer children than piles? In this case, the algorithm will still work but some piles will remain unused.
arrow_right_alt
What if some piles have fewer candies than the required amount? The binary search will help find the maximum possible value for candy allocation.
arrow_right_alt
Consider an optimized solution that minimizes redundant calculations during the binary search process.

help

常见问题

外企场景

继续练习

#2234 花园的最大总美丽值 #2250 统计包含每个点的矩形数目 #2251 花期内花的数目