---
# System prepended metadata

title: Koko Eating Bananas(Medium)

---

## 853. Koko Eating Bananas(Medium)

### 題目描述
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

 

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23
 

Constraints:

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

### 解題思路

* 二元搜尋法
* 計算吃完香蕉的最短時數

### 程式碼

```cpp=
int hoursRequired(int* piles, int pilesSize, int h, int speed) {
    int hours = 0;
    for (int i = 0; i < pilesSize; i++) {
        hours += (piles[i]+speed-1)/speed;
    }
    return hours;
}

int maxElement(int* piles, int pilesSize) {
    int maxElem = piles[0];
    for (int i = 0; i < pilesSize; i++) {
      maxElem = fmax(maxElem, piles[i]);
    }
    return maxElem;
}

int minEatingSpeed(int* piles, int pilesSize, int h){
    int l = 1;
    int r = maxElement(piles, pilesSize);
    while (l < r) {
      int mid = (l + r)/2;
      int hours = hoursRequired(piles, pilesSize, h, mid);
      if (hours <= h){
        r = mid;
      }else if (hours > h){
        l = mid + 1;
      }
    }
    return r;
}
```

### 時間/空間複雜度
* 時間複雜度: $O(nlogn)$
* 空間複雜度: $O(1)$
![image.png](https://hackmd.io/_uploads/rJ6qpwk7T.png)

