875. Koko Eating Bananas
有 n 堆的香蕉，其中第 i 堆的香蕉有 piles[i] 個，
現在每小時可以選擇其中一堆並吃掉最多 k 個香蕉，
如果那堆不滿 k 個也只能吃掉那堆的全部，下一小時才能再選其他堆來吃。
給定 h 代表要在 h 小時內吃完 n 堆香蕉，求 k 的最小值是多少。
Constraints:
- 1 <= piles.length <= 10^4
- piles.length <= h <= 10^9
- 1 <= piles[i] <= 10^9
Example 1:
Input: piles = [3,6,7,11], h = 8
Output: 4
Explanation:
第一堆需要 1 小時 (4*0 < 3 <= 4*1)
第二堆需要 2 小時 (4*1 < 6 <= 4*2)
第三堆需要 2 小時 (4*1 < 7 <= 4*2)
第四堆需要 3 小時 (4*2 < 11 <= 4*3)
每小時吃 4 個剛好能在 8 小時內吃完 (且每小時吃 3 個不行)
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
解題思路:
若 k' 可以在 h 小時內吃完，則 k' + 1 也一定可以，
因為有單調性所以可以對答案做二分搜。
因為 h >= piles.length，所以每小時吃 max(piles) 一定可以在 h 小時內吃完，
每小時吃 0 個一定吃不完，
答案落在 (0, max(piles)]。
k' 能在 h 小時內吃完 if sum_i (ceil(piles[i] / k)) <= h，
注意整數除法會變整數跟加總可能會 overflow。
C++ code:
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int l = 0, r = *max_element(piles.begin(), piles.end());
while(l + 1 < r){
int mid = (l + r) / 2;
long long hours = 0;
for(auto p : piles){
hours += ceil((double)p / mid);
}
if(hours <= h) r = mid;
else l = mid;
}
return r;
}
};