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;
}
};