[two points] leetcode1011 Capacity To Ship Packages Within D Days

A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

The question ： Divide an array into... At most days Share （ continuity ）, Sum each group The minimum of the maximum .

Ideas ： greedy + Two points answer

Suppose that the carrying capacity of the ship is x when , Can be in days Deliver all packages within days , So as long as the carrying capacity is greater than x, You can also days Deliver all packages within days .

Conclusion ：

There is a common carrying capacity 【 Lower limit 】x0, When x>=x0 when , Can be in days Deliver all packages within days , When x<x0 when , Cannot be in days Deliver all packages within days .

therefore ,x0 Is the answer that needs to be found .

You can use the binary search method to find x0.

Determine the problem ： Given carrying capacity x, Can it be in days All the packages will be delivered within days ？

Solve by greedy means ：

Because you must follow the array Weights In the order of the packages , So we start with an array weights Start traversing the first element of , Arrange for successive packages to be delivered on the same day . When the weight of this parcel is greater than the carrying capacity x when , You need to take out the last package , On a new day , And continue to traverse . When we traverse the entire array , You get the minimum number of days to transport .

Compare the minimum number of days to be shipped with days Compare , And then we can solve this problem .

Be careful check The logic of ：

class Solution {
    public int shipWithinDays(int[] weights, int days) {
      int l=1,r=500*50000;
      while(l<r){
          int mid=(l+r)/2;
          int need=1,cur=0;
          for(int w:weights){
              if(w>mid)need=(int)1e6;
              if(cur+w>mid){
                  need++;
                  cur=0;
              }
              
              cur+=w;
          }
          if(need<=days){
              r=mid;
          }else l=mid+1;
      }
      return l;
    }
}