问题描述
传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。传送带上的第i个包裹的重量为 weights[i]。每一天，都会按给出重量的顺序往传送带上装载包裹。装载的重量不会超过船的最大运载重量。返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
示例 1：
输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10
请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
示例 2：
输入：weights = [3,2,2,4,1,4], D = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4
示例 3：
输入：weights = [1,2,3,1,1], D = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1
解决方案
如果采用暴力法去取每一个值，并判断是否符合题意，这时会发现，如果weights的值有很多个时，会出现超时的情况，这时就会用到二分查找算法来降低算法时间复杂度。
二分查找算法：
a为取值的下限，b为取值的上限，tar为当前取值
判断tar过大还是过小，如果tar过大那么，上限b缩短为tar，tar变为(tar+a)/2；
同理，过小下限a就变为tar，tar变为(tar+b)/2；
一直持续下去，直到满足题意所给出的条件即可。
代码解决及解析
1.定义一个jg函数用来处理所需的运载天数，其中tar为运载的能力(即题目中的最大运载量)，s用来记录当前的重量，day用来记载所用天数；即得到运载能力(tar)所对应的运载天数(day)；
2.创建一个a,b分别表示运载能力的上下限，a表示下限，b表示上限，因为下限a的最小值一定是=max(weights)，这样才能保证weights中的每个值都能运载，不会超载；同理当运载能力上限b=sum(weights)时，只需1天就能运载完毕；故得出载重上下限a,b;
3.其次，定一个res数组用来装入运载能力(tar)所对应的运载天数(day)<D时的tar值,即满足题意的tar值，tar为二分查找的中值，即(a+b)/2，即上下限值和的一半，当然在每个判断条件之后，会采用二分法来改变上下限的值。(注意：该题中的tar值类型为float,故在加入res中时应该是int(tar),判断时，也应该转化为int类型)
4.加入res的值为day<=D时的int(tar)值,因为此时的tar所对应的day<=D，满足题意；
class Solution: def shipWithinDays(self, weights: List[int], D: int) -> int: def jg(weights,tar):#tar为运载能力 s,day=0,0 for i in weights:#遍历weights的每天重量 if s+i>tar:#当前的重量 + 当该天的包裹重量 > 当前最大运载能力tar；当天包裹重量就一起不能运载，会超重 day,s=day+1,i #天数+1，s当前重量就变为该天的包裹重量 else:#反之，当前重量+该天包裹重量 s+=i return day+1 a,b=max(weights),sum(weights)#a表示运载能力下限，b表示运载能力上限 if len(weights)<D:#如果运载天数大于包裹的个数，直接返回下限,因为就算每天只运一个包裹也不会超过D,故返回下限即可； return a res,tar=[],(a+b)/2 while int(tar) not in res:#当tar存在于res中时终止循环 day=jg(weights,tar) if day<D:#运载能力(tar)所对应的运载天数(day)<D时，表示运载能力过大故采用二分法，上限b应该缩短到tar，tar应该变为当前(tar+a)/2(代码中b=tar，故采用的b代替tar)，后者day>D同理。 res.append(int(tar)) b=tar tar=(a+b)/2 elif day==D:#如果运载能力(tar)所对应的运载天数(day)=D时，表示运载能力所对应的天数不能再减少了，此时，就需要(运载能力(tar)-1)来逐步逼近所取满足条件的tar的最小值； res.append(int(tar)) tar=tar-1 else: a=tar tar=(b+a)/2 return max(min(res),max(weights)) |
结语
该博客主要讲解了如何用二分法思考并解决包裹最低运载问题，当然该题以及二分查找算法的最重要的还是取值(tar)上下限的变化，与暴力法相比，二分查找算法来求解，极大的减少了搜索的范围，从而降低了算法时间复杂度。
