Force deduction solution summary 875- coco who likes bananas

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ：

Power button

describe ：

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

Tips ：

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/koko-eating-bananas
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  The simplest way to solve this problem , We can 1 Start trying , Try until you reach the maximum value in the array . But the time complexity is too high , Can cause a timeout .
*  So the way to solve this problem is binary search , Set up left and right, If sum No timeout , be right Move to the left , whereas left To the right . Finally, finding the critical point is the result we want .

Code ：

public int minEatingSpeed(int[] piles, int h) {
        int right = 0;
        for (int i : piles) {
            right = Math.max(i, right);
        }
        if (piles.length == h) {
            return right;
        }
        int result = 1;
        int left = 1;
        while (true) {
            int middle = (left + right) / 2;
            if (left > right) {
                break;
            }
            long sum = 0;
            for (int i : piles) {
                sum += i / middle;
                if (i % middle != 0) {
                    sum++;
                }
            }
            if (sum <= h) {
                result = middle;
                right = middle + (right - middle) / 2 - 1;
            } else {
                left = middle + 1;
            }
        }
        return result;
    }