I. Title Description:

Ke Ke likes bananas. There were N piles of bananas and piles I had piles of bananas. The guard has left and will be back in H hours.

Coco can determine the rate at which she eats the banana, K (roots per hour). Every hour, she will choose a bunch of bananas and eat K of them. If there are less than K bananas in the pile, she will eat all the bananas in the pile and will not eat any more bananas for an hour.

Ke liked to eat slowly, but still wanted to eat all the bananas before the guards came back.

Returns the minimum speed at which she can eat all bananas in H (K is an integer).

Example 1:

Input: piles = [3,6,7,11], H = 8

Input: piles = [30,11,23,4,20], H = 5 Output: 30 Example 3:

Inputs: piles = [30,11,23,4,20], H = 6 outputs: 23

Tip:

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

2. How to solve the problem

Generalization of binary search problems, four steps:

  1. Determining the variable x is generally the minimum or maximum that you want
  2. Let’s say that f(x) f is a function that increases or decreases as x increases
  3. Determine the target f (x) =target constraint
  4. Determine the left and right boundaries

2.1 Increasing and decreasing functions

Increasing function:

Decreasing function:

2.2 the problem solving

Follow the steps:

2.2.1. Determine the x

X is the number of bananas eaten per hour: x roots per hour.

2.2.2 determine f (x)

You see target is hour, so f of x is the total number of hours it takes to eat all the bananas.

int f(int[] piles,x){ int hours=0; for(int i=0; i<piles.length; i++){ hours+=piles[i]/x; if(piles[i]%x>0){ hours++; } } return hours; }Copy the code

2.2.3. Determine constraints

Target = = H. Equivalent to finding the element equal to target.

2.2.4 Left and right boundaries are determined

1 <= piles[I] <= 10^9, so right piles 1000000000. Of course, because X represents the number of banana roots eaten, it can’t exceed the maximum number of bananas in N piles, so it’s possible to iterate to get the maximum in piles[I].

Note that f is a decreasing function!

public int minEatingSpeed(int[] piles, int H) { int left = 1; int right = 1000000000 + 1; While (left panel right) {int mid = left + (right-left) / 2; If (F (haemg, mid) == H) {// To search left piles, I had to shrink right piles; } else if (F (piles, mid) H) {// The return value of f(x) will need to be large; } else if (f(piles, mid) › H) {// Need to have f(piles, mid) return smaller left = mid + 1; } } return left; }Copy the code

Finally, because we want to minimize x, we are essentially finding the first element to the left of f(x)==target!

So the code looks like this:

class Solution { public int minEatingSpeed(int[] piles, int h) { int left=1; int right=1000000000; while(left<=right){ int mid=left+(right-left)/2; int cost= eatCostTime(mid,piles); If (cost> h){// Set eatCostTime to return a smaller value because it is a decrement function. So the left boundary is left=mid+1; }else if(cost< h){// Set eatCostTime to return a higher value because it is decremented. So I'm adjusting the left margin right=mid-1; }else{ System.out.println("mid: "+mid); if(0==mid||eatCostTime(mid-1,piles)! =h){ return mid; }else{ right=mid-1; }}} return left; } public int eatCostTime(int x,int[] piles){ int hour=0; for(int i=0; i<piles.length; i++){ hour+=piles[i]/x; if(piles[i]%x>0){ hour++; } } return hour; }}Copy the code

Three original problem connection:

Ke Ke likes bananas