leetcode-875

LeetCode 875. 爱吃香蕉的珂珂

1 题目描述

• 题目链接：875. 爱吃香蕉的珂珂

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

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

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

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

示例1：

输入: piles = [3,6,7,11], h = 8
输出: 4

示例2：

输入: piles = [30,11,23,4,20], h = 5
输出: 30

示例3：

输入: piles = [30,11,23,4,20], h = 6
输出: 23

2 思路

  二分法经典题目，即在一个升序数组中找到一个值满足要求。这里的值其实就是吃的速度，而升序数组其实就是1-很大的数。根据题目中给出的1 <= piles[i] <= 1e9的条件可知，最大速度不大于1e9.因此，左边界初始化为1，右边界初始化为1e9，然后进行二分查找，当满足要求（即用当前的速度可以在不大于h的时间里吃完香蕉）时更新答案并减小速度进行尝试.

class Solution {    
    // 判断以当前速度能否吃完香蕉
    bool check(const vector<int> piles, int h, int m){
        int cnt = 0;
        for(int i: piles){
            cnt += i/m;
            cnt += i%m ? 1 : 0;
        }
        return cnt <= h;
    }
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int l = 1, r = INT_MIN;
        for(int i: piles){
            r = std::max(r, i);
        }
        if(piles.size() == h)   return r;
        int ans;
        while(l <= r){
            int m = l + (r - l) / 2;
            if(check(piles, h, m)){ // 可以吃完香蕉
                ans = m;            // 更新答案
                r = m - 1;          // 减小速度继续进行尝试
            }else{
                l = m + 1;          // 没法吃完，说明速度过慢，需要加快速度
            }           
        }
        return ans;
    }
};