# 「力扣」第 875 题：爱吃香蕉的珂珂（中等）
我写的题解地址：https://leetcode-cn.com/problems/koko-eating-bananas/solution/er-fen-cha-zhao-ding-wei-su-du-by-liweiwei1419/
1、速度越小，耗时越多； 2、搜索的是速度。因为题目限制了珂珂一个小时之内只能选择一堆香蕉吃，因此速度最大值就是这几堆香蕉中，数量最多的那一堆。速度的最小值是 1（其实还可以再分析一下下界是多少）；
3、还是因为珂珂一个小时之内只能选择一堆香蕉吃，因此：每堆香蕉吃完的耗时 = 这堆香蕉的数量 / 珂珂一小时吃香蕉的数量，这里的 / 在不能整除的时候，需要上取整。
#include <iostream>
#include <vector>
using namespace std;
class Solution {
private:
int calculateSum(vector<int> &piles, int speed) {
int sum = 0;
for (int pile : piles) {
sum += (pile + speed - 1) / speed;
}
return sum;
}
public:
int minEatingSpeed(vector<int> &piles, int H) {
int maxVal = 1;
for (int pile : piles) {
maxVal = max(maxVal, pile);
}
// 速度最小的时候，耗时最长
int left = 1;
// 速度最大的时候，耗时最短
int right = maxVal;
while (left < right) {
int mid = left + (right - left) / 2;
if (calculateSum(piles, mid) > H) {
// 耗时太多，说明速度太慢了，下一轮搜索区间在
// [mid + 1, right]
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
from typing import List
class Solution:
def minEatingSpeed(self, piles: List[int], H: int) -> int:
left = 1
right = max(piles)
while left < right:
mid = (left + right) // 2
if self.__calculate_sum(piles, mid) > H:
left = mid + 1
else:
right = mid
return left
def __calculate_sum(self, piles, speed):
res = 0
for pile in piles:
res += (pile + speed - 1) // speed
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22