LC875.爱吃香蕉的阿珂

• 原题链接

  珂珂喜欢吃香蕉。这里有 堆香蕉，第 堆中有 根香蕉。警卫已经离开了，将在 小时后回来。 珂珂可以决定她吃香蕉的速度 （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 根。如果这堆香蕉少于 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。 返回她可以在 小时内吃掉所有香蕉的最小速度 （ 为整数）。

• 示例 1：

  输入：piles = [3,6,7,11], h = 8 输出：4

• 示例 2：

  输入：piles = [30,11,23,4,20], h = 5 输出：30

• 示例 3：

  输入：piles = [30,11,23,4,20], h = 6 输出：23

• 提示：
• 
• 

• 

  思路：用二分代替暴力遍历

• 如果阿珂吃香蕉的速度非常快，那么一定可以在预定的时间内吃掉全部的香蕉

• 逐步降低吃香蕉的速度，直到刚好卡在预定的时间上即可

• 对于“吃香蕉的速度”这个序列而言，本质上就是找“右区间的左端点”，用二分查找代替暴力遍历。

  代码：

  class Solution {
  public:
    bool check(int speed, vector<int> piles, int h) {
        int all_time = 0;
        for (int pile : piles) {
            all_time += ((pile - 1) / speed  + 1);
        }
        return all_time <= h;
    }
    int minEatingSpeed(vector<int>& piles, int h) {
        // 吃的越快，那么需要的h就越小
        // 逐步降低吃的速度，那么h就慢慢升高
        // 相当于找右区间的左端点
        int left = 1, right = 1e9 + 9;
        while (left < right) {
            int mid = (left + right) / 2;
            if (check(mid, piles, h)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
  };