LeetCode 2226中等二分答案
每个小孩最多分到的糖果数 图解题解
这道题到底在问什么
给定糖果堆 candies 与孩子数 k。每堆可拆分但不能合并，每个孩子拿到相同数量（同一堆切出的份），求每个孩子最多能拿到的颗数；分不出则返回 0。
- 输入
- candies=[5,8,6], k=3
- 输出
- 5 （切成 5、5、5 三份）
最优解：一步一步想明白
- 3记住「二分每人颗数 x：总份数 = Σ(堆 // x)，≥ k 就往大试、否则往小收」，下面每帧都在套它。
- 4每人最少 1 颗、最多不超过最大堆 917 颗，所以在 [1, 917] 里二分 x。每试一个 x，就数所有堆按 x 切出的总份数，和 6 比。
- 5试每人拿 459 颗：每堆切出 263÷459=0、917÷459=1、145÷459=0、528÷459=1、76÷459=0、392÷459=0，共 2 份（绿色堆是能切出至少 1 份的）。2 < 6，不够分。
- 6不够分，每人 459 颗太多了，范围左移到 [1, 458]，往小了试。
- 7试每人拿 229 颗：每堆切出 263÷229=1、917÷229=4、145÷229=0、528÷229=2、76÷229=0、392÷229=1，共 8 份（绿色堆是能切出至少 1 份的）。8 ≥ 6，够分！
- 8够分，先把 229 记成目前最好答案 ans=229；还想拿更多，范围右移到 [230, 458]。
- 9试每人拿 344 颗：每堆切出 263÷344=0、917÷344=2、145÷344=0、528÷344=1、76÷344=0、392÷344=1，共 4 份（绿色堆是能切出至少 1 份的）。4 < 6，不够分。
- 10不够分，每人 344 颗太多了，范围左移到 [230, 343]，往小了试。
- 11试每人拿 286 颗：每堆切出 263÷286=0、917÷286=3、145÷286=0、528÷286=1、76÷286=0、392÷286=1，共 5 份（绿色堆是能切出至少 1 份的）。5 < 6，不够分。
- 12不够分，每人 286 颗太多了，范围左移到 [230, 285]，往小了试。
- 13试每人拿 257 颗：每堆切出 263÷257=1、917÷257=3、145÷257=0、528÷257=2、76÷257=0、392÷257=1，共 7 份（绿色堆是能切出至少 1 份的）。7 ≥ 6，够分！
- 14够分，先把 257 记成目前最好答案 ans=257；还想拿更多，范围右移到 [258, 285]。
- 15试每人拿 271 颗：每堆切出 263÷271=0、917÷271=3、145÷271=0、528÷271=1、76÷271=0、392÷271=1，共 5 份（绿色堆是能切出至少 1 份的）。5 < 6，不够分。
- 16不够分，每人 271 颗太多了，范围左移到 [258, 270]，往小了试。
- 17试每人拿 264 颗：每堆切出 263÷264=0、917÷264=3、145÷264=0、528÷264=2、76÷264=0、392÷264=1，共 6 份（绿色堆是能切出至少 1 份的）。6 ≥ 6，够分！
- 18够分，先把 264 记成目前最好答案 ans=264；还想拿更多，范围右移到 [265, 270]。
- 19试每人拿 267 颗：每堆切出 263÷267=0、917÷267=3、145÷267=0、528÷267=1、76÷267=0、392÷267=1，共 5 份（绿色堆是能切出至少 1 份的）。5 < 6，不够分。
- 20不够分，每人 267 颗太多了，范围左移到 [265, 266]，往小了试。
- 21试每人拿 265 颗：每堆切出 263÷265=0、917÷265=3、145÷265=0、528÷265=1、76÷265=0、392÷265=1，共 5 份（绿色堆是能切出至少 1 份的）。5 < 6，不够分。
- 22不够分，每人 265 颗太多了，范围左移到 [265, 264]，往小了试。
- 23范围收空，二分结束。一路记下的最大可行 x = 264，就是每个孩子最多能分到的糖果数。注意「能分到 264 颗」靠的是总份数 ≥ 6，而不是正好等于 6。
⚠️ 容易写错的地方
✗ 错：二分糖果堆的下标
✓ 对：二分的是「每人拿几颗 x」这个答案
答案本身单调可行,才能二分;堆下标无此单调性
✗ 错：总份数要正好等于 k
✓ 对：总份数 ≥ k 即可行
多切出的份不分给人也没关系,只要够 k 个人每人 x 颗
✗ 错：区间开闭/收缩规则混用
✓ 对：全程闭区间:可行 left=mid+1、不可行 right=mid−1
和代码一致才不会死循环或漏解
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def maximumCandies(self, candies: List[int], k: int) -> int:
left, right = 1, max(candies, default=0)
ans = 0
while left <= right:
mid = (left + right) // 2
pieces = sum(c // mid for c in candies)
if pieces >= k:
ans = mid
left = mid + 1
else:
right = mid - 1
return ansC++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maximumCandies(vector<int>& candies, long long k) {
int left = 1, right = candies.empty() ? 0 : *max_element(candies.begin(), candies.end());
int ans = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
long long pieces = 0;
for (int c : candies) pieces += c / mid;
if (pieces >= k) ans = mid, left = mid + 1;
else right = mid - 1;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int maximumCandies(int[] candies, long k) {
int right = 0;
for (int c : candies) right = Math.max(right, c);
int left = 1, ans = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
long pieces = 0;
for (int c : candies) pieces += c / mid;
if (pieces >= k) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
}复杂度
时间
O(n·log M)
M=最大堆;二分 logM 次,每次 O(n) 数份数
空间
O(1)
只用 left/right/ans 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 每个小孩最多分到的糖果数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
怎么确定二分的上界?+
每人最多不可能超过最大的那一堆(再多连一份都切不出),所以上界 = max(candies);下界是 1(至少 1 颗)。k 很大、总糖不够时,二分自然落到 ans=0。
「二分答案」一般什么时候用?+
当「直接求最优值」难、但「给定一个候选值、判断它是否可行」容易,且可行性随候选值单调时,就二分这个答案值、用判定函数收缩。本题判定 = 总份数是否 ≥ k,典型可二分。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 每个小孩最多分到的糖果数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。