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

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

1. 题目分析

题目给出了若干堆糖果，我们可以将每一堆拆分成更小的糖果堆，再将它们分配给 k 个孩子。

这里有几个需要注意的条件：

• 每个孩子分到的糖果数量必须相同。
• 每个孩子只能拿一堆糖果，不能将不同堆的糖果合并。
• 不要求把所有糖果分完，多余的糖果可以不分配。

我们的目标就是找到每个孩子最多能够分到多少颗糖果。

先看题目给出的两个样例。

样例 1：

candies = [5, 8, 6]
k = 3

可以将原来的三堆糖果 [5, 8, 6] 拆成 [5, 5, 3, 5, 1]。

这样就有了三堆数量为 5 的糖果，刚好可以分给三个孩子，每人一堆。剩下的两堆不用分配。

因此，这个样例的答案是 5。

样例 2：

candies = [2, 5]
k = 11

这次只有 7 颗糖果，却需要分给 11 个孩子。

即使每人只分 1 颗，也无法满足所有孩子，因此答案只能是 0。

从第二个样例可以看出，我们可以先判断糖果总数是否小于孩子数量。如果连每人一颗都不够，就直接返回 0，不必继续计算。

2. 二分答案

对于剩下的情况，我们需要找到一个最大的糖果数量，使得每个孩子都能分到这么多。

最直接的想法，是从 1 开始，逐个尝试每个孩子能够分到的糖果数量。不过，这样需要检查很多候选答案，效率并不理想。

仔细想想，这里的答案其实具有单调性。

假设我们尝试让每个孩子分到 res 颗糖果：

• 如果 res = 3 可以满足所有孩子，那么比 3 更小的正整数也一定可以。
• 如果 res = 5 已经无法满足所有孩子，那么比 5 更大的数量也一定不行。

因为每个孩子分到的糖果越多，原来的每一堆糖果能够拆出的份数就越少。

所以，随着 res 增大，候选答案会呈现出这样的规律：

候选答案：  1    2    3    4    5    6    7
是否可行：  ✓    ✓    ✓    ✓    ✗    ✗    ✗
                              ↑
                       第一个不可行的位置

这就符合二分查找的使用条件。

我们可以寻找第一个不可行的答案，然后减去 1，得到最大的可行答案。

3. 如何判断一个答案是否可行？

二分查找还需要一个判断函数 check(res)，用来检查当前尝试的糖果数量是否满足要求。

假设某一堆有 x 颗糖果，而我们希望每个孩子分到 res 颗。

那么，这堆糖果最多可以拆出：

x // res

份符合要求的糖果。

这里使用整除，是因为不足 res 颗的剩余糖果无法单独分给一个孩子。

对所有糖果堆进行相同的计算，再将结果累加，就能得到最多可以分配给多少个孩子：

sum(x // res for x in a)

如果这个数量大于等于 k，说明当前答案可行；反之，则说明糖果不够分配。

不过，代码中的 check() 判断的是当前答案是否不可行：

def check(res):
    return sum(x // res for x in a) < k

也就是说：

• 返回 True：当前糖果数量太大，无法满足 k 个孩子。
• 返回 False：当前糖果数量可以满足要求，还可以尝试更大的值。

这样就能配合二分查找，找到第一个不可行的位置。

4. 二分查找的边界处理

这份代码使用 lo 和 hi 表示二分查找的左右边界：

lo, hi = 1, 10**12 + 10

由于前面已经排除了糖果总数小于 k 的情况，此时每人至少分到 1 颗是可行的，因此可以从 1 开始查找。

hi 则取了一个足够大的值，确保它一定不可行。

每次循环都取中间位置：

i = (lo + hi) >> 1

这里的 >> 1 相当于对非负整数进行整除 2，用于计算二分中点。

接下来根据 check(i) 的结果更新边界：

if check(i):
    hi = i
else:
    lo = i + 1

如果 check(i) 返回 True，说明当前答案已经不可行，那么第一个不可行的位置可能就是 i，也可能在它左边，所以将 hi 更新为 i。

反之，如果当前答案可行，就说明第一个不可行的位置一定在 i 的右边，因此令 lo = i + 1。

不断缩小范围，直到 lo == hi，就找到了第一个不可行的糖果数量。

由于我们要找的是最大的可行答案，所以最后返回：

return lo - 1

5. 代码实现

Python 代码：

class Solution:
    def maximumCandies(self, a: List[int], k: int) -> int:
        # 如果糖果总数小于总人数,那么直接就无法分,返回一个0
        if sum(a) < k:
            return 0
        
        # 答案区间为1,10^12+10,其中0我们已经排除掉了,题目中k的数据范围最大是10^12,我们加10可以保险一点.
        lo, hi = 1, 10**12 + 10

        def check(res):
            # res就是我们要尝试的答案,把每一堆都按res尽可能多的分堆.
            return sum(x // res for x in a) < k

        while lo < hi:
            i = (lo + hi) >> 1
        # 利用二分的思想,res从1到n是递增的,但是sum(x // res for x in a)却是递减的.
        # 举个简单的例子,res是1满足答案,res是2满足答案,res是3不满足答案.那么3-1的2就是能分的最大数量,
        # 所以最后我们找到的就是刚好不满足答案的res.减去1就是能分的最多的数量
            if check(i):
                hi = i
            else:
                lo = i + 1
        return lo - 1

C++ 代码：

class Solution {
public:
    int maximumCandies(vector<int>& a, long long k) {
        long long sum = 0;
        for (auto& x : a) {
            sum += x;
        }
        if (sum < k) {
            return 0;
        }
        long long lo = 1, hi = pow(10, 12) + 10;
        while (lo < hi) {
            long long i = (lo + hi) >> 1;
            if (check(i, a, k)) {
                hi = i;
            } else {
                lo = i + 1;
            }
        }
        return lo - 1;
    }
    int check(long long& res, vector<int>& v, long long& k) {
        long long sum = 0;
        for (auto& x : v) {
            sum += x / res;
        }
        return sum < k;
    }
};

这里的 Python 和 C++ 实现采用了相同的二分思路，主要区别在于语法和数据类型。

C++ 中使用 long long 保存糖果总数、孩子数量以及二分边界，避免在处理较大数值时发生整数溢出。

另外，C++ 的 check() 函数通过引用接收参数。其中，数组使用引用传递，可以避免复制整个 vector。函数只读取数据并统计能够拆出的糖果份数，不会修改原数组。

6. 复杂度分析

假设糖果堆的数量为 n，二分查找的上界为 U。

每次调用 check()，都需要遍历所有糖果堆，计算能够拆出的份数，因此单次检查的时间复杂度为 O(n)。

二分查找最多进行 O(log U) 次检查，所以整体时间复杂度为：

O(n log U)

额外空间复杂度为 O(1)，因为只需要保存少量变量，不需要额外开辟与输入规模成正比的存储空间。

这道题的关键在于二分答案，而不是二分数组下标。

当我们发现“每个孩子分到的糖果数量”越大，满足要求就越困难时，就可以利用这种单调性，通过二分查找确定最大可行答案。