875. Leetcode, a banana lover

875. Coco, who loves bananas - Power button （LeetCode）

Power button 2022/6/7 A daily topic

Coco likes bananas . Here you are n Make bananas , The first i There is... In the pile piles[i] A banana . The guards have left , Will be in h Come back in hours .

Coco can decide how fast she eats bananas k （ Company ： root / Hours ）. Every hour , She will choose a bunch of bananas , Eat from it k root . If this pile of bananas is less than k root , She will eat all the bananas in this pile , Then I won't eat more bananas in an hour .

Coco likes to eat slowly , But still want to eat all the bananas before the guards come back .

She can go back to h Minimum speed to eat all bananas in hours k（k Integers ）.

Example 1：

Input ：piles = [3,6,7,11], h = 8

Output ：4

Tips ：

• 1 <= piles.length <= 10^4
• piles.length <= h <= 10^9
• 1 <= piles[i] <= 10^9

Problem analysis

Basic binary answer question , Binary enumeration possible k, see k Can you finish eating all bananas within the specified time , If you can explain that our speed can continue to be small , If not, it means that our speed should be increased .

As for judging whether you can finish eating bananas within the specified time , Enumerable mid Traversal array , If you can divide the current element , It means that the time taken to finish eating this pile of bananas is （ The current element /mid), If you can't divide it, then ++. According to the sum of the counter value after traversing the array h To judge the size of , Less than or equal to h It means that we can finish within the specified time , Not vice versa .

AC Code

class Solution {
public:
    bool check(int mid,int h,vector<int>& piles)
    {
        int res=0,n=piles.size();
        for(int i=0;i<n;i++)
        {
            if(piles[i]%mid!=0)res++;
            res+=piles[i]/mid;
        }
        return res<=h;
    }
    int minEatingSpeed(vector<int>& piles, int h) {
        int l=1,r=1e9;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(check(mid,h,piles))r=mid;
            else l=mid+1;
        }
        return l;
    }
};