爱吃香蕉的珂珂 图解题解

珂珂每小时只吃一堆，这道题到底在求哪个速度

给几堆香蕉 piles 和警卫回来前的小时数 h，珂珂每小时挑一堆、以固定速度 k 根吃，一堆吃光了剩下时间也不换堆。求能在 h 小时内吃完全部香蕉的最小整数速度 k。题面 piles=[3,6,7,11]、h=8 时答案是 4：速度 4 刚好 8 小时吃完，再慢一档就超时。

为什么从 1 到最大堆一个个试速度会白扫一大截

速度最小取 1、最大取 11（最大那堆 11 根，速度 11 一小时吃光，再快没意义）。一个笨办法是从 1 起逐个速度试，每试一个就把四堆各要几小时加起来、看超不超 h。可最坏要一路试到最大那档才停，扫过的速度数和这段速度范围（1 到最大堆）一样多，时间 O(n·max)；范围大到 10⁹ 就挨个试不动了。

速度和「来不来得及」之间，藏着一条能二分的分界线

把每个速度的总小时数排一排会看出：速度越大，吃完的总时间只会越短、越来得及——这就是单调（沿一个方向走、不回头）。于是所有速度被切成两半，左边都太慢、来不及，右边都够快、来得及，答案正是界线上第一个够快的速度。有了单调分界，就能用二分查找逼近它，不必挨个试。这里点破一句：二分的不是某个数组下标，而是所有可能的吃速。这种不直接推公式、而是猜一个速度再验证行不行的思路，叫二分答案。

判定函数怎么写，够快和太慢又各往哪半收

先把「行不行」做成判定函数（输入一个速度、回答够不够快的小函数）hours(k)：每堆各要 ⌈香蕉数 ÷ k⌉ 小时（⌈⌉ 是向上取整，吃不满一小时也算一整小时），加起来就是这速度的总耗时。二分在区间 [lo, hi] 取中点 mid 算 hours(mid)：≤ h 够快，把 hi 收到 mid（mid 可能正是最小，得留）；> h 太慢，mid 连左边全不行，把 lo 跳到 mid+1。缩到 lo 和 hi 撞上，那格就是最小可行速度。

拿题面 piles、h=8 逐轮列出 mid 和判定

起点 lo=1、hi=11。第一轮 mid=(1+11)//2=6，hours(6)=1+1+2+2=6 ≤ 8 够快，hi 收到 6。第二轮 lo=1、hi=6，mid=3，hours(3)=1+2+3+4=10 > 8 太慢，lo 跳到 4。第三轮 lo=4、hi=6，mid=5，hours(5)=1+2+2+3=8 ≤ 8 够快，hi 收到 5。第四轮 lo=4、hi=5，mid=4，hours(4)=1+2+2+3=8 ≤ 8 够快，hi 收到 4。此时 lo=hi=4，循环停，返回 4。

lo 起点搁 0，判定里的除法当场崩

二分把速度档数压到约 log max，每档 hours() 扫 n 堆，时间 O(n·log max)、空间 O(1)。lo 起点得从 1 起，写成 0 时 ⌈p ÷ 0⌉ 当场除零崩掉。够快时收缩只能写 hi=mid，写成 hi=mid-1 会把可能就是答案的 mid 丢出区间，返回值偏大一档。太慢那支要写 lo=mid+1，若写成 lo=mid，等 lo、hi 只差一格时 mid 永远卡在 lo、区间缩不动，就死循环。

Python

import math
def minEatingSpeed(piles, h):
    def hours(k):                  # 速度 k 吃完要几小时
        return sum(math.ceil(p / k) for p in piles)
    lo, hi = 1, max(piles)         # 速度区间 [1, max]
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h:        # 够快
            hi = mid               #   试更慢
        else:                      # 太慢
            lo = mid + 1           #   加速
    return lo                      # 最小可行速度

C++

int minEatingSpeed(vector<int>& piles, int h){
    auto hours = [&](long long k){
        long long t = 0;
        for(int p : piles) t += (p + k - 1) / k;   // 向上取整
        return t;
    };
    int lo = 1, hi = *max_element(piles.begin(), piles.end());
    while(lo < hi){
        int mid = lo + (hi - lo) / 2;
        if(hours(mid) <= h) hi = mid;   // 够快, 试更慢
        else lo = mid + 1;              // 太慢, 加速
    }
    return lo;
}

Java

public int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 0;
    for (int p : piles) hi = Math.max(hi, p);   // 速度上界 = 最大堆
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (hours(piles, mid) <= h) {           // 够快
            hi = mid;                           //   试更慢
        } else {                                // 太慢
            lo = mid + 1;                       //   加速
        }
    }
    return lo;                                  // 最小可行速度
}

private long hours(int[] piles, int k) {
    long t = 0;
    for (int p : piles) t += (p + k - 1) / k;   // 向上取整
    return t;
}