珂珂喜歡吃香蕉。這里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警衛(wèi)已經(jīng)離開(kāi)了，將在 H 小時(shí)后回來(lái)。

珂珂可以決定她吃香蕉的速度 K （單位：根/小時(shí)）。每個(gè)小時(shí)，她將會(huì)選擇一堆香蕉，從中吃掉 K 根。如果這堆香蕉少于 K 根，她將吃掉這堆的所有香蕉，然后這一小時(shí)內(nèi)不會(huì)再吃更多的香蕉。

珂珂喜歡慢慢吃，但仍然想在警衛(wèi)回來(lái)前吃掉所有的香蕉。

返回她可以在 H 小時(shí)內(nèi)吃掉所有香蕉的最小速度 K（K 為整數(shù)）。

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

在線(xiàn)評(píng)測(cè)地址: lintcode領(lǐng)扣

樣例 1:

輸入: piles = [3,6,7,11], H = 8
輸出: 4
解釋?zhuān)?->42,7->42,11->43,3->41

樣例 2:

輸入: piles = [30,11,23,4,20], H = 5
輸出: 30
解釋?zhuān)?->301,11->301,20->301,23->301,30->30*1

【題解】

采用二分的解法

public class Solution {
    /**
     * @param piles: an array
     * @param H: an integer
     * @return: the minimum integer K
     */
    public int minEatingSpeed(int[] piles, int H) {
        // Write your code here
        int l = 1, r = 1000000000;
        while (l < r) {
            int m = (l + r) / 2, total = 0;
            for (int p : piles) 
                total += (p + m - 1) / m;
            if (total > H) 
                l = m + 1; 
            else 
                r = m;
        }
        return l;
    }

更多語(yǔ)言代碼參見(jiàn)：leetcode/lintcode題解