当前:LC875 · 爱吃香蕉的珂珂 · 首次出现于 Day 47 · 路径:顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

LC875 · Koko Eating Bananas · 二分

爱吃香蕉:对速度二分,用小时数检查

一小时只能啃一堆。速度 k 吃完第 i 堆要 ⌈pile/k⌉ 小时,把各堆加起来和 h 比,就能对 k 二分。

速度下界 1,上界 max(piles)。can(k) 把每堆的 ⌈p/k⌉ 加总,总和 ≤ h 则 k 可行。可行收高界,不可行抬低界,收敛的 low 是最小速度。⌈p/k⌉ 用整数 (p+k−1)/k。时间 O(n log M),空间 O(1)。

时间 O(n log M)空间 O(1)结论先行 · 全文约 6 节
导读

这是 LeetCode 875. Koko Eating Bananas。大白话:有若干堆香蕉 piles[i],守卫离开 h 小时。Koko 选定一个整数速度 k,每个小时只吃一堆:这堆不少于 k 根就吃掉 k 根,不足 k 根就把这堆吃完,剩余时间不能去下一堆。要在 h 小时内吃完所有堆,求最小的 k。

主例 piles = [3, 6, 7, 11],h = 8。k = 4 时,四堆分别要 1、2、2、3 小时,合计 8,刚好。k = 3 时是 1+2+3+4=10,超过 8。k = 5 也是 8 小时,但不是最小。答案是 4。

直接猜最小 k 没有公式。缺的是单调检查:k 越大,每堆小时数不增,总时间不增。某个 k 能吃完,更快的都能;某个 k 吃不完,更慢的更不行。于是对速度二分。

先会算「这个速度要几小时」

规则里最容易漏的一句:一小时不能换堆。3 根的堆用 k=4 吃,仍占满 1 小时,省下来的额度作废。所以第 i 堆的耗时是 ⌈piles[i]/k⌉,不是 piles[i]/k 再跨堆拼。总时间是各堆向上取整之和,和 h 比大小就是 can(k)。

k 变大,每一项 ⌈p/k⌉ 单调不增,总和单调不增。can 从假变真之后不会再变假。这是二分的通行证。上界取 max(piles) 就够:再快也是每堆至少 1 小时,总时间的下限是堆数;h 若小于堆数,题目保证有解,实际上 h 至少是堆数。

用手走检查。k=3:⌈3/3⌉=1,⌈6/3⌉=2,⌈7/3⌉=3,⌈11/3⌉=4,合计 10 > 8,不可行。演示唯一一帧就是这 10 小时。k=4:⌈3/4⌉=1,⌈6/4⌉=2,⌈7/4⌉=2,⌈11/4⌉=3,合计 8,可行。整数除法写成 (p+k−1)/k,避免浮点。k 从 1 起,不会除零。

单调can(k) 随 k 增大从假变真,一旦为真就一直为真。要找的是这段真后缀的左端点,也就是最小可行速度。
速度 k=3:piles = [3,6,7,11] → 1+2+3+4 = 10 小时 > 8,不可行
36711
h = 8速度 3需要 10 小时 > h ✗⌈3/3⌉+⌈6/3⌉+⌈7/3⌉+⌈11/3⌉ = 1+2+3+4 = 10

对速度二分:能吃完就试更慢

搜索区间 [1, max(piles)]。主例是 [1, 11]。mid = lo + (hi−lo)/2,跑 can(mid)。能吃完则 hi = mid,mid 可能就是最小速度,不能丢掉;吃不完则 lo = mid+1。lo < hi 时继续,结束时 lo 就是最小 k。

主例第一拍 lo=1、hi=11,mid=6。⌈3/6⌉+⌈6/6⌉+⌈7/6⌉+⌈11/6⌉=1+1+2+2=6 ≤ 8,可行,hi=6。演示第一帧。下一拍 mid=3,上面已经算过 10 > 8,不可行,lo=4。区间变成 [4, 6]。演示第二帧取 mid=5:1+2+2+3=8,可行,hi=5。再取 mid=4:也是 8,可行,hi=4。lo 与 hi 在 4 相遇,演示第三帧收敛。

4 和 5 都能吃完,二分留下的是左端 4。若把可行写成 lo = mid,会粘在较大的可行值上,主例可能停在 5。方向必须是「可行压低、不可行抬高」。

二分速度区间,用 can 判断去留
36711
h = 8[low=1, high=11]mid=6can(6)=6 ≤ 8 → 可行,high=6

Go:答案二分

solution.goGo
func minEatingSpeed(piles []int, h int) int {
can := func(k int) bool {
t := 0
for _, p := range piles { t += (p + k - 1) / k }
return t <= h
}
lo, hi := 1, slices.Max(piles)
for lo < hi {
mid := lo + (hi-lo)/2
if can(mid) { hi = mid } else { lo = mid + 1 }
}
return lo
}

1can(k) 把各堆 (p+k−1)/k 加总。主例 k=3 得到 10,k=4 得到 8。

2不要用浮点再 ceil。整数公式和 ⌈p/k⌉ 同值,k≥1 不会除零。

3区间 [1, max]。再快也省不下「每堆至少一小时」。

4可行 hi=mid,不可行 lo=mid+1。主例从 [1,11] 收到 4,不是 5。

总结

对速度二分;检查是各堆 ⌈p/k⌉ 之和是否 ≤ h。主例 3 要 10 小时,4 要 8 小时。

  • 一小时不能换堆,所以是向上取整再求和,不是总根数除以 k。
  • k 越大总时间越短,可行区间是后缀,二分找左端。
  • 主例 can(6)=6 收高界,can(3)=10 抬低界,最后停在 4。
同族题目
LC1011在 D 天内送达包裹的能力LC410分割数组的最大值LC704二分查找