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日星期四