题目描述
珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。  

珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。

解题思路

二分查找

  1. 确定解空间,在解空间实现二分查找.解空间就是 [1,max(piles)]
  2. 如果速度 k 吃不完所有香蕉,那么所有小于等于 k 的解都可以被排除
  3. 珂珂一个小时之内只能选择一堆香蕉吃,因此:每堆香蕉吃完的耗时 = 这堆香蕉的数量 / 珂珂一小时吃香蕉的数量。需要上取整

代码模板

def bisect_left(nums, x):
    # 内置 api
    bisect.bisect_left(nums, x)
    # 手写
    l, r = 0, len(A) - 1
    while l <= r:
        mid = (l + r) // 2
        if A[mid] >= x: r = mid - 1
        else: l = mid + 1
    return l

本题代码

    static boolean possible(int[] piles, int H, int K) {
        int time = 0;
        for (int p : piles) {
            time += (p + K - 1) / K;
        }
        return time <= H;
    }

    static int minEatingSpeed(int[] piles, int H) {
        int l = 1;
        int r = Arrays.stream(piles).max().getAsInt();
        while (l < r) {
            int mi = (l + r) / 2;
            if (!possible(piles, H, mi)) {
                l = mi + 1;
            } else {
                r = mi;
            }
        }
        return l;
    }

Q.E.D.