题解#在 D 天内送达包裹的能力#

'''
解题思路：
二分查找：左边界为数组最大值，右边界为数组元素的和，寻找船的最低运载能力
'''
class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:

        W = weights
        n = len(weights)
        #print(W)        
        wMin = max(W)
        wMax = sum(W)

        # 最低运载能力为w时，是否可在days天内完成
        def isOK(w):            
            t = 0
            day = 0
            for i in range(n):
                t += W[i]
                if t>w:
                    day += 1
                    t = W[i]
            day += 1
            #print('day=',day)            
            if day<=days:
                return True
            else:
                return False

        resMin = isOK(wMin) 
        if resMin:
            return wMin

        resMax = True            
        while wMin<wMax-1:            
            wMid = (wMin+wMax)//2
            resMid = isOK(wMid)
            if resMid:
                resMax = resMid
                wMax = wMid
            else:
                resMin = resMid
                wMin = wMid

        #print('wMax=',wMax)      
        return wMax      

t = Solution().shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)       # 15 
#t = Solution().shipWithinDays([3,2,2,4,1,4], 3)        # 6
#t = Solution().shipWithinDays([1,2,3,1,1], 4)   # 3
print(t)