面试算法73:狒狒吃香蕉

2023-12-25 12:28:49

题目

狒狒很喜欢吃香蕉。一天它发现了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;
    }
}

文章来源:https://blog.csdn.net/GoGleTech/article/details/135196586
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。