题目描述

Koko喜欢吃香蕉，有N堆香蕉，第i堆有piles[i]个香蕉。门卫现在离开了并且会在H个小时以后回来。

Koko能够决定自己吃香蕉的速度K(个/小时)，每个小时她都会选择某一堆香蕉，然后从那一堆吃掉K个香蕉，如果那一堆的香蕉数少于K，那么她就会吃掉那一堆的所有香蕉并且在那个小时不会再吃更多的香蕉。Koko希望尽可能慢地吃香蕉，但同时她又希望在门卫回来之前把香蕉吃完。

我们需要计算最小的正整数K，使得她能在H小时内吃掉所有的香蕉。

样例

输入: piles = [3,6,7,11], H = 8
输出: 4
说明：K=4时，吃掉每一堆香蕉所需的时间为[1,2,2,3]，加起来正好为8，
而当K=3时，吃掉每一堆香蕉所需的时间为[1,2,3,4]，加起来为10>8，因此最小的K为4.

算法

(二分查找)

K可能的范围为[1, m], m表示piles中的最大值，即m=max{piles[i]}，考虑用二分查找的方式找到最小的满足条件的K，即二分查找K的lower bound，对于每个中间值mid，判断所需要的时间T是否小于H，需要注意的是当mid所需要的时间正好满足所需时间为H，还不能停止查找，右指针需要继续左移直到找到最小的K为止。

时间复杂度分析：二分查找复杂度为$O(log(m))$(m=max{piles[i]})，对于每个值都需要$O(n)$(n为数组长度）遍历一遍数组判断所需用的时间，因此复杂度为$O(nlog(m))$。

C++ 代码

class Solution {
public:
    int needTime(vector<int>piles, int K){//计算速度为K时吃完所有香蕉所需要的时间。
        int T = 0;
        for(int i =0;i<piles.size();i++){
            T += ceil(float(piles[i])/K);//上取整
        }
        return T;
    }
    int minEatingSpeed(vector<int>& piles, int H) {
        int max = 0;
        for(int i = 0;i<piles.size();i++){//计算max{piles[i]}
            if(piles[i]>max)
                max=piles[i];
        }
        if(H==piles.size())
            return max;
        int l = 1;//K的查找范围为[1, max]
        int r = max;
        while(l<r){
            int mid = (l+r)/2;
            int T = needTime(piles, mid);
            if(T>H)
                l = mid+1;
            if(T<=H)//查找lower bound
                r = mid;
        }
        return r;
    }
};