###### tags: `Leetcode` `medium` `binary search` `array` `python` `c++`

# 875. Koko Eating Bananas

## [題目連結:] https://leetcode.com/problems/koko-eating-bananas/

## 題目:

## 解題想法:
* 此題為有n串香蕉，第i串有piles[i]根香蕉
* 守衛h小時回來
* 設一小時能吃k根香蕉
* 吃完第i串後無法再同一小時內吃另外第j串
* 若第i串有x根香蕉，且x<k，則依舊需要等該小時過完，才能繼續下一串，**意思為: 若有餘數需無條件進位1小時**
* 求k使得能以**最慢速度**吃完所有香蕉

* Binary Search二分法變化題:
* **搜查範圍為1~max(piles)之間**
* 大於max肯定不是最慢速度了
* 二分找適當的速度之下可以全部吃完且滿足時間內

## Python:

class Solution(object):
    def minEatingSpeed(self, piles, h):
        """
        :type piles: List[int]
        :type h: int
        :rtype: int
        """
        #二分搜的變化
        #範圍為1與max(piles)之間 大於max肯定不是最慢速度
        #二分找適當的速度之下可以全部吃完且滿足時間內
        minSpeed=1
        maxSpeed=max(piles)
        while minSpeed<=maxSpeed:
            mid=(minSpeed+maxSpeed)/2
            totalHour=0
            for val in piles:
                carry=0 if val%mid==0 else 1 #餘數需多加1小時
                totalHour+=(val/mid)+carry
            if totalHour<=h: #吃太快了
                maxSpeed=mid-1
            else:
                minSpeed=mid+1
        return minSpeed

## C++:
* C++找最大原素: ***max_element**
* https://blog.csdn.net/A_Eagle/article/details/7373165
* 因為此題範圍 piles.length <= h <= 109
* **第11行用long long int**，避免overflow用

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int min=1;
        int max=*max_element(piles.begin(), piles.end());
        while (min<=max){
            int mid=min+(max-min)/2;
            long long int totalHours=0;
            for (auto val: piles){
                int carry= (val%mid==0)? 0: 1;
                totalHours+=int(val/mid)+carry;
            }
            if (totalHours<=h)
                max=mid-1;
            else
                min=mid+1;
        }
        return min;
    }
};