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

先看样例 1：[5,8,6] 可以拆成 [5,5,3,5,1]，三个孩子各取一堆 5，所以每个孩子最多分到 5 个。这里每个孩子只能取一堆，多余的堆可以不分配。

样例 2 的糖果为 [2,5]，总共只有 7 个，却有 11 个孩子，连每人 1 个都不够，因此答案为 0。

可以把每个孩子分到的数量 res 作为候选答案，在区间 [lo, hi] 内二分。res 越大，每堆能拆出的份数越少：如果某个数量已经无法分给 k 个孩子，更大的数量也不可行。因此，可以寻找第一个不可行的数量，再减一，得到最大的可行答案。

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;
    }
};

C++ 代码中的上界取到了 10 的 12 次方，超过 int 的范围，需要使用 long long。check 通过引用接收参数，其中对数组的引用避免了复制整个容器；函数只读取并统计这些数据，没有修改原数组。