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

标签: 数组 二分查找

难度: Medium

给你一个 下标从 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 <= 105
  • 1 <= candies[i] <= 107
  • 1 <= k <= 1012

Submission

运行时间: 164 ms

内存: 28.6 MB

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        total = sum(candies)
        if total < k: return 0
        left, right = 1, total // k
        while left <= right:
            mid = left + (right - left) // 2
            cnt = sum([i // mid for i in candies])
            if cnt >= k:
                left = mid + 1
            else:
                right = mid - 1
        return right

Explain

该题解采用了二分查找的策略来确定每个小孩能分到的最大糖果数。首先计算所有糖果的总和，如果总和小于小孩的数量k，则无法给每个小孩至少分配一颗糖果，直接返回0。设置二分查找的范围left为1（最小可能的糖果数），right为total // k（平均每个小孩最多能分到的糖果数）。在这个范围内，使用二分查找不断尝试一个中间值mid，计算如果每个小孩分到mid颗糖果，可以满足多少小孩。如果可以满足的小孩数cnt大于等于k，则增大搜索范围的下限left（意味着可能可以分配更多糖果），否则减小搜索范围的上限right。最终，right将会是满足条件的最大糖果数目。

时间复杂度: O(n log(maxCandy))

空间复杂度: O(1)

class Solution:
    def maximumCandies(self, candies: List[int], k: int) -> int:
        total = sum(candies)  # 计算糖果总数
        if total < k: return 0  # 如果糖果总数少于小孩数，返回0
        left, right = 1, total // k  # 设置二分搜索的范围
        while left <= right:
            mid = left + (right - left) // 2  # 计算中间值
            cnt = sum([i // mid for i in candies])  # 计算每个小孩分到mid颗糖果时，可以满足的小孩数
            if cnt >= k:
                left = mid + 1  # 如果能满足的小孩数大于等于k，尝试增加糖果数
            else:
                right = mid - 1  # 否则减少糖果数
        return right  # 返回最大可能的糖果数

Explore

设置左边界为1是基于假设每个小孩至少能分得一颗糖果开始考虑的。对于题目要求每个小孩至少分到一颗的情况，这是合理的。如果某些糖果数量少于1，即某些糖果堆为空，这并不影响算法的正确性，因为这些堆不会对满足小孩数量的计算产生贡献。因此，左边界为1是一个有效的起始点。

当`cnt`大于等于`k`时，意味着当前的`mid`值是可行的，即至少可以满足`k`个小孩每人得到`mid`颗糖果。因此，为了找到最大可能的糖果分配数量，我们可以尝试增加`mid`的值，即将`left`设置为`mid + 1`，继续探索是否存在更大的满足条件的`mid`值。这是因为我们的目标是最大化每个小孩能得到的糖果数。

设置右边界为`total // k`是基于所有糖果平均分配给每个小孩的最大可能数目。这并没有直接考虑单个糖果堆中的最大值。在某些情况下，这可能导致未能利用单堆糖果的大量剩余。一个改进方法是将右边界设置为`min(total // k, max(candies))`，这样可以确保右边界不会低于任何一个糖果堆的最大值，从而不会错过可能的最大糖果数。

使用`sum([i // mid for i in candies])`的方式确实有效地利用了每堆糖果可以分割的特性，通过计算每堆糖果能提供的至少`mid`数量的糖果的组数来确定总体可以满足的小孩数。这种方法在计算分配糖果时是高效的，因为它直接通过整数除法得到每堆糖果能分出多少组符合条件的糖果数，从而统计总的可满足小孩数。