题目

Koko loves to eat bananas. There are N piles of bananas, the i-th 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 won’t eat any more bananas during this hour.

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

Return the minimum integer K such that she can eat all the bananas within H hours.

1
2
Input: piles = [30,11,23,4,20], H = 5
Output: 30

题目的意思就是找到一个数K,能够在H次将所有piles减去,要满足条件下最小的K。

解答

这种找到某个满足条件的数的题目大多都需要二分法,范围1~max(piles),每次判断是否能够在H时间内吃完:

  • 如果能够吃完,看能不能将K变小一些
  • 如果不能在规定时间吃完,将K变大,mid就不用再考虑,直接lowP = mid + 1

在判断能否吃完的函数,每次总时间减去当前piles[i]需要的时间,如果还没吃完所有食物,时间就不够了,说明不能在规定时间内吃完

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
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int H) {
int maxP = piles[0];

for (auto p: piles) {
maxP = max(p, maxP);
}
int lowP = 1;
while (lowP < maxP) {
int mid = (lowP + maxP) / 2;
if (canEating(piles, mid, H)) {
maxP = mid;
} else {
lowP = mid + 1;
}
}
return lowP;
}
bool canEating(vector<int> & piles, int K, long H) {
for (int index = 0; index < piles.size(); index++) {
H -= (int)ceil((double)piles[index] / K);
if (H < 0) return false;
}
return true;
}
};

时间复杂度O(nlgn)