875. Koko Eating Bananas

解題思路

直覺想到這題是在解等式，假設答案為 x，那該等式為 ceil(piles[i]/i) 的 sum 要小於等於 h，找出最小的 x。

只是要怎麼求 x？很酷的方法是想成 x 的所有可能範圍值介在 1 ~ max(piles)，然後用 binary search 的方式縮小範圍。如果 mid 是可以的，那就再往左邊試看看更小的還有無機會(right shift)；如果不行代表 left 要往右移一點。

程式碼

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int maxPile = 0;
        for(int i=0; i<piles.size(); i++)
            maxPile = max(maxPile, piles[i]);

        int left = 1, right = maxPile, mid;
        while(left <= right)
        {
            mid = (left + right) / 2;
            long long int hour = 0;
            for(int i=0; i<piles.size(); i++)
                hour += ceil((double)piles[i] / mid);
            if(hour > h)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }
};