题目描述
思路解析动画文字版
记住「二分每人颗数 x:总份数 = Σ(堆 // x),≥ k 就往大试、否则往小收」,下面每帧都在套它。
每人最少 1 颗、最多不超过最大堆 917 颗,所以在 [1, 917] 里二分 x。每试一个 x,就数所有堆按 x 切出的总份数,和 6 比。
试每人拿 459 颗:每堆切出 263÷459=0、917÷459=1、145÷459=0、528÷459=1、76÷459=0、392÷459=0,共 2 份(绿色堆是能切出至少 1 份的)。2 < 6,不够分。
不够分,每人 459 颗太多了,范围左移到 [1, 458],往小了试。
试每人拿 229 颗:每堆切出 263÷229=1、917÷229=4、145÷229=0、528÷229=2、76÷229=0、392÷229=1,共 8 份(绿色堆是能切出至少 1 份的)。8 ≥ 6,够分!
够分,先把 229 记成目前最好答案 ans=229;还想拿更多,范围右移到 [230, 458]。
试每人拿 344 颗:每堆切出 263÷344=0、917÷344=2、145÷344=0、528÷344=1、76÷344=0、392÷344=1,共 4 份(绿色堆是能切出至少 1 份的)。4 < 6,不够分。
不够分,每人 344 颗太多了,范围左移到 [230, 343],往小了试。
试每人拿 286 颗:每堆切出 263÷286=0、917÷286=3、145÷286=0、528÷286=1、76÷286=0、392÷286=1,共 5 份(绿色堆是能切出至少 1 份的)。5 < 6,不够分。
不够分,每人 286 颗太多了,范围左移到 [230, 285],往小了试。
试每人拿 257 颗:每堆切出 263÷257=1、917÷257=3、145÷257=0、528÷257=2、76÷257=0、392÷257=1,共 7 份(绿色堆是能切出至少 1 份的)。7 ≥ 6,够分!
够分,先把 257 记成目前最好答案 ans=257;还想拿更多,范围右移到 [258, 285]。
试每人拿 271 颗:每堆切出 263÷271=0、917÷271=3、145÷271=0、528÷271=1、76÷271=0、392÷271=1,共 5 份(绿色堆是能切出至少 1 份的)。5 < 6,不够分。
不够分,每人 271 颗太多了,范围左移到 [258, 270],往小了试。
试每人拿 264 颗:每堆切出 263÷264=0、917÷264=3、145÷264=0、528÷264=2、76÷264=0、392÷264=1,共 6 份(绿色堆是能切出至少 1 份的)。6 ≥ 6,够分!
够分,先把 264 记成目前最好答案 ans=264;还想拿更多,范围右移到 [265, 270]。
试每人拿 267 颗:每堆切出 263÷267=0、917÷267=3、145÷267=0、528÷267=1、76÷267=0、392÷267=1,共 5 份(绿色堆是能切出至少 1 份的)。5 < 6,不够分。
不够分,每人 267 颗太多了,范围左移到 [265, 266],往小了试。
试每人拿 265 颗:每堆切出 263÷265=0、917÷265=3、145÷265=0、528÷265=1、76÷265=0、392÷265=1,共 5 份(绿色堆是能切出至少 1 份的)。5 < 6,不够分。
不够分,每人 265 颗太多了,范围左移到 [265, 264],往小了试。
范围收空,二分结束。一路记下的最大可行 x = 264,就是每个孩子最多能分到的糖果数。注意「能分到 264 颗」靠的是总份数 ≥ 6,而不是正好等于 6。
边界先想清:分不出返回 0;份数够即可不必正好。
面试重点:上界 = 最大堆;识别「判定易+单调」就上二分答案。
参考代码
from typing import Listclass 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 ans复杂度
- 时间:O(n·log M),M=最大堆;二分 logM 次,每次 O(n) 数份数
- 空间:O(1),只用 left/right/ans 几个变量
易错点
面试追问把动画讲成自己的话
追问怎么确定二分的上界?
追问「二分答案」一般什么时候用?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
分割数组的最大值
LeetCode 410 · 困难 · 沿着 二分答案套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题