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

思路

乍一看，这题很像贪心题；但把数据范围和目标条件捋顺以后，会发现二分答案其实更稳，也更好写。

题目的核心不是'怎么分'，而是能不能分出每个小孩都拿到 x 颗糖果。如果某个 x 可行，那比它更小的值一定也可行；反过来，如果 x 不可行，那更大的值也不可能可行。这个单调性正好适合二分。

因此我们要做的事情就很明确了：

• 二分一个'每个小孩能分到的糖果数' mid
• 检查当前 mid 是否能分给至少 k 个小孩
• 如果可以，就尝试继续往更大的值找，并记录答案
• 如果不可以，就缩小范围

这里有个细节要注意：糖果总数可能很大，sum、left、right、mid 以及 k 都应该用 long，不然很容易在边界数据上出问题。

如何判断 mid 是否可行

对每堆糖果 t 来说，如果每个小孩拿 mid 颗，那么这堆最多能分给 t / mid 个小孩。把所有堆能提供的小孩数累加起来，只要总数达到 k，说明当前 mid 可行。

这个判断不需要额外的贪心技巧，直接遍历就够了。

代码

class Solution {
    public int maximumCandies(int[] candies, long k) {
        long sum = 0;
        for (int c : candies) {
            sum += c;
        }

        // 糖果总量都不够分给 k 个小孩时，直接返回 0
        if (sum < k) return 0;

        long left = 1, right = sum;
        long ans = 0;

        while (left <= right) {
            long mid = (left + right) / ;
             (check(candies, mid, k)) {
                ans = mid;
                left = mid + ; 
            }  {
                right = mid - ;
            }
        }

         () ans;
    }

       {
         ( t : candies) {
            k -= t / num;
             (k <= )  ;
        }
         ;
    }
}