面试算法73：狒狒吃香蕉

题目

狒狒很喜欢吃香蕉。一天它发现了n堆香蕉，第i堆有piles[i]根香蕉。门卫刚好走开，H小时后才会回来。狒狒吃香蕉喜欢细嚼慢咽，但又想在门卫回来之前吃完所有的香蕉。请问狒狒每小时至少吃多少根香蕉？如果狒狒决定每小时吃k根香蕉，而它在吃的某一堆剩余的香蕉的数目少于k，那么它只会将这一堆的香蕉吃完，下一个小时才会开始吃另一堆的香蕉。
例如，有4堆香蕉，表示香蕉数目的数组piles为[3，6，7，11]，门卫将于8小时之后回来，那么狒狒每小时吃香蕉的最少数目为4根。如果它每小时吃4根香蕉，那么它用8小时吃完所有香蕉。如果它每小时只吃3根香蕉，则需要10小时，不能在门卫回来之前吃完。

分析

虽然还不知道狒狒1小时至少要吃几根香蕉才能在门卫回来之前吃完所有的香蕉，但知道它吃香蕉的速度的范围。显然，它每小时至少要吃1根香蕉。由于它1小时内只吃一堆香蕉，因此它每小时吃香蕉数目的上限是最大一堆香蕉的数目，记为max根。也就是说，狒狒吃香蕉的速度应该在最小值1根和最大值max根的范围内。
再以求狒狒用8小时吃完4堆数目分别为[3，6，7，11]的最慢速度为例分析二分查找的过程。显然，狒狒每小时至少吃1根香蕉，每小时最多吃11根香蕉，于是先计算以中间值每小时吃6根香蕉的速度吃完所有香蕉所需要的时间。如果每小时吃6根香蕉，吃完4堆香蕉分别需要1小时、1小时、2小时、2小时，总共需要6小时，少于8小时。接着判断每小时吃6根香蕉是不是能在8小时吃完的最慢速度。判断的办法是让狒狒尝试慢一点的速度，每小时吃5根香蕉。如果狒狒每小时吃5根香蕉，它吃完4堆香蕉分别需要1小时、2小时、2小时、3小时，总共需要8小时。因此，每小时吃6根香蕉不是最慢的速度。接下来可以在1根到5根的范围内查找。1根到5根的中间值是3根。如果狒狒每小时吃3根香蕉，它吃完4堆香蕉分别需要1小时、2小时、3小时、4小时，吃完所有香蕉总共需要10小时。因此，它需要吃得快一些。接下来在4根到5根的范围内查找。接着尝试4根到5根的中间值4根。如果狒狒每小时吃4根香蕉，那么它吃完4堆香蕉分别需要1小时、2小时、2小时、3小时，吃完所有香蕉需要8小时。接着判断每小时吃4根香蕉是不是能在8小时吃完所有香蕉的最慢速度。如果狒狒每小时只吃3根香蕉，那么它需要10小时才能吃完所有香蕉，因此每小时吃4根香蕉的确是它能在8小时吃完所有香蕉的最慢速度。

解

public class Test {
    public static void main(String[] args) {
        int[] piles = {3, 6, 7, 11};
        System.out.println(minEatingSpeed(piles, 8));
    }

    public static int minEatingSpeed(int[] piles, int H) {
        int max = Integer.MIN_VALUE;
        for (int pile : piles) {
            max = Math.max(max, pile);
        }

        int left = 1;
        int right = max;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int hours = getHours(piles, mid);
            if (hours <= H) {
                if (mid == 1 || getHours(piles, mid - 1) > H) {
                    return mid;
                }

                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        return -1;
    }

    private static int getHours(int[] piles, int speed) {
        int hours = 0;
        for (int pile : piles) {
            hours += (pile + speed - 1) / speed;
        }

        return hours;
    }
}