算法笔记

labuladongNotes

1. 运输货物（二分搜索）————待整理二分搜索笔记
   题目描述：给你一个正整数数组 weights 和一个正整数D，其中weights代表一系列货物，weights[i] 代表第个货物重量，货物不可分割且必须按顺序运输。求货船在D天内能运完所有货物的最小运载能力。
   【解析】
   首先，先确定运输能力范围，最小是max（weights）；最大是sum（weights）；
   因为求最小运载能力，所以对 运输能力进行线性搜索 ，也就是用求左边界的二分搜索。

intshipWithinDays(int [] weights,int D){
	int left=getMax(weights);
	int right=getSum(weights)**+1**;
	while(left<right){
		if(canFinish(weights,D,mid)){
		right=mid;		 //防止有多种满足情况，所以让右边界不断像左收缩
		else {
  			left=mid**+1**;
			}        
		}
	}
	return left;
}
boolean canFinish（int weights[],int D ,int cap）{
int time=0;
int result=0;
for(int n:weights){
   		 while(res<=cap){
   		 res+=n;	
		}
 		 time++;
  		 res=n;
	}  
	     return time<=D;	
}