【LeetCode】875. Keke who loves bananas

题目

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

示例 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

提示：

1 <= piles.length <= 104
piles.length <= h <= 109
1 <= piles[i] <= 109

题解

在范围内,寻找最优解mid
使用二分法
Select left and right boundary values,Get one each time through the loopmid,Iterate over the array to calculate the cumulative sum of the time it took to eat each bunch of bananastimes
若用时大于h,则增大mid来缩小times
If the time is less than or equal toh,则减小mid来增大times

这一题类似于【LeetCode】1760.袋子里最少数目的球

class Solution {
    
public:
    int minEatingSpeed(vector<int>& piles, int h) {
    
        int left = 1;
        //int right = INT_MAX;
        int right = *max_element(piles.begin(),piles.end());
        int res = 0;
        while(left < right)
        {
    
            int mid = left + ((right - left)>>1);
            
            int times = 0;
            for(int& it:piles)
                times += it/mid + (it%mid!=0);
            
            if(times<=h)
            {
    
                //cout<<"减小mid来增大times："<<left<<"=="<<mid<<"=="<<right<<"==>"<<times<<endl;
                right = mid;
            }
            else
            {
    
                //cout<<"增大mid来减小times："<<left<<"=="<<mid<<"=="<<right<<"==>"<<times<<endl;
                left = mid+1;
            }
                
        }
        return right;
    }
};