爱吃香蕉的珂珂

2021-04-26

875. 爱吃香蕉的珂珂

难度中等164收藏分享切换为英文接收动态反馈

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

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

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

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

示例 1：

1 2	输入: piles = [3,6,7,11], H = 8 输出: 4

示例 2：

1 2	输入: piles = [30,11,23,4,20], H = 5 输出: 30

示例 3：

1 2	输入: piles = [30,11,23,4,20], H = 6 输出: 23

提示：

1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9

通过次数30,497

提交次数65,121

二分答案

将答案的最小值和最大值作为搜索的左边界和右边界，每次搜索判断搜索到的值是否满足题目的条件（暴力计算即可），如果满足条件，那么就降低当前的条件，如果当前搜索到的值不满足条件，那么提升当前的条件。

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int n = piles.length;
        int l = 0, r = (int)1e9;
        while(l<r){
            int m = l+(r-l)/2;
            int time = 0;
            // 这里是关键步骤，一下没想起来
            for(int p:piles){
                if(p<m){
                    time++;
                }else{
                    time += (int)Math.ceil(p*1.0/m);
                }
            }
            if(time<=h){
                r = m;
            }else{
                l = m + 1;
            }
        }
        return l;
    }
}

官方题解

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int lo = 1;
        int hi = 1_000_000_000;
        while (lo < hi) {
            int mi = (lo + hi) / 2;
            if (!possible(piles, H, mi))
                lo = mi + 1;
            else
                hi = mi;
        }

        return lo;
    }

    // Can Koko eat all bananas in H hours with eating speed K?
    public boolean possible(int[] piles, int H, int K) {
        int time = 0;
        for (int p: piles)
            time += (p-1) / K + 1;
        return time <= H;
    }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/koko-eating-bananas/solution/ai-chi-xiang-jiao-de-ke-ke-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

875. 爱吃香蕉的珂珂

二分答案

官方题解

同类型题目