Binary search application
Question 1:
Packages on the conveyor belt must be transported from one port to another within days.
The weight of the ＾ I ＾ th package on the conveyor belt is ＾ weights[i]. Every day, we will load packages on the conveyor belt in the order of given weights. The weight we load will not exceed the maximum carrying weight of the ship.
Return the minimum carrying capacity of the ship that can deliver all packages on the conveyor belt within {days.
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5 Output: 15 Explanation: The minimum ship load of 15 can deliver all packages within 5 days, as follows: Day 1: 1, 2, 3, 4, 5 Day 2: 6, 7 Day 3: 8 Day 4: 9 Day 5: 10 Please note that the goods must be shipped in the given order, so it is not allowed to use a ship with a load capacity of 14 and divide the packaging into (2, 3, 4, 5), (1, 6, 7), (8), (9), (10).
Example 2:
Input: weights = [3,2,2,4,1,4], days = 3 Output: 6 Explanation: The minimum ship load of 6 can deliver all packages within 3 days, as follows: Day 1: 3, 2 Day 2: 2, 4 Day 3: 1, 4
Example 3:
Input: weights = [1,2,3,1,1], D = 4 Output: 3 Explanation: Day 1: 1 Day 2: 2 Day 3: 3 Day 4: 1, 1
Tips:
- 1 <= days <= weights.length <= 5 * 104
- 1 <= weights[i] <= 500
1 class Solution { 2 public int shipWithinDays(int[] weights, int days) { 3 int l=0,r=1; 4 for (int w:weights){ 5 l=Math.max(l,w); 6 r+=w; 7 } 8 while (l<r) { 9 int mid=(l+r)/2; 10 if (f(weights,mid)<=days){ 11 r=mid; 12 } 13 else if (f(weights,mid)>days) { 14 l=mid+1; 15 } 16 } 17 return l; 18 } 19 20 public int f(int[] w,int cap){ 21 int ans=1,t=cap; 22 for (int i=0;i<w.length;i++){ 23 if (t>=w[i]) { 24 t-=w[i]; 25 continue; 26 }else { 27 t=cap; 28 t-=w[i]; 29 ans++; 30 } 31 } 32 //System.out.println(cap+" "+ans); 33 return ans; 34 } 35 }
Taking the carrying capacity as the independent variable, the carrying days is a function of the non increase of the independent variable, the lower bound is the maximum value of all goods, and the upper bound is the weight of all goods. The binary search is carried out to search the left boundary that meets the requirements of days.
Question 2:
875. Ke Ke, who likes bananaslabuladong problem solutionthinking
Ke Ke likes bananas. There are ， piles of bananas here, and ， piles[i] bananas in pile ， I. The guard has left and will be back in {hours.
Ke Ke can decide how fast she eats bananas ， K (unit: root / hour). Every hour, she will choose a pile of bananas and eat ， K ， roots from them. If this pile of bananas is less than ， K ， roots, she will eat all the bananas in this pile, and then she will not eat more bananas in this hour
Ke Ke likes to eat slowly, but still wants to eat all the bananas before the guard comes back.
Returns the minimum speed K at which she can eat all bananas in H ＾ hours (K ＾ is an integer).
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 <= 10^9
- 1 <= piles[i] <= 10^9
1 class Solution { 2 public int minEatingSpeed(int[] piles, int h) { 3 int l=1,r=1000000000+1; 4 while (l<r) { 5 int mid=(l+r)/2; 6 if (f(piles,mid)<=h){ 7 r=mid; 8 }else { 9 l=mid+1; 10 } 11 } 12 return l; 13 } 14 15 public int f(int[] nums,int x){ 16 int ans=0; 17 for (int num:nums){ 18 ans+=num/x; 19 if (num%x!=0) ans++; 20 } 21 return ans; 22 } 23 }
Similarly, it is transformed into the left boundary of binary search.