题目链接: 2226. 每个小孩最多能分到多少糖果

这个题我们先看一下样例1.[5,8,6],将8和6进行拆分,变成[5,5,3,5,1]然后三个孩子分别拿走3个5,每个孩子最多能分到的糖果就是5个.然后看题意,每个孩子只能拿一堆.多余的堆是可以舍弃不要的.

然后样例2的话,糖果是[2,5],加起来才是7而已,却有11个人,一人一个也完全不够.所以每个人最多只能分到0个.

我们就可以观察到,这个题是求最优解的,并且答案res存在一个确定的,连续的区间[lo,hi].并且是单调的.我们就可以拿答案res去一个一个尝试,然后采用二分的去提高效率.最后找到正确的答案.

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++的话一定要注意使用long long ,10的12次方已经超过int的可存储范围了.并且check函数使用&直接引用原数据提高效率,因为这里我们只做一些求和之类的操作,并不会修改原数据.