LeetCode875. Koko Eating Bananas(二分)
- Medium
- Accepted:13,211
- Submissions:28,647
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.
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
Note:
1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9
链接
https://leetcode.com/problems/koko-eating-bananas
题意
小 A 喜欢吃香蕉,现在有 n 堆香蕉,每堆 piles [i] 个。吃香蕉的规则如下:有 H 个小时可以吃香蕉,小 A 每小时可以吃 K 个香蕉,但每小时只能选择一堆香蕉,如果这堆香蕉个数小于 K,那么就吃完所有的,这一个小时不再吃别的香蕉,如果这堆香蕉个数大于 K,那么就只能吃 K 个。现求最小的 K,使得小 A 能在 H 小时内吃完所有的香蕉。
题解
很容易知道这题就是一个二分,K 可以取的最小值为 1,最大值为 n 堆香蕉中数量最多的那一堆(的数量),然后我们对 K 进行二分,使得 K 的左边都不满足在 H 个小时内吃完所有的香蕉,K 的右边都满足在 H 个小时内吃完所有的香蕉,那么答案就是 K。实际上就是二分查找大于等于 x 的第一个值。
代码
- Runtime: 72 ms, faster than 38.20% of C++ online submissions for Koko Eating Bananas.
- Memory Usage: 10.3 MB, less than 47.57% of C++ online submissions for Koko Eating Bananas.
- class Solution {
- public:
- int minEatingSpeed(vector<int>& piles, int H) {
- int n = piles.size();
- sort(piles.begin(), piles.end());
- int l = 1, r = piles[n - 1];
- while (l < r)
- {
- int mid = (l + r) >> 1;
- if (isValid(piles, H, mid)) // mid符合条件,答案在[l, mid]中
- r = mid;
- else
- l = mid + 1;
- }
- return l;
- }
-
- bool isValid(vector<int>& piles, int H, int x)
- {
- int sum = 0;
- for (int i = 0; i < piles.size(); ++i)
- sum += (piles[i] - 1) / x + 1; // 巧妙的处理,相当于 piles[i] / x + piles[i] % x;
- return sum <= H;
- }
- };
The end.
2019 年 6 月 13 日 星期四