給出所有貨物的重量weights，以及需要在days天內(nèi)運輸完，求運載量最少需要多少，運輸貨物需要按weights順序進行
因為貨物的傳輸是確定順序的所以比較簡單，二分答案，每次判斷是否能在days天內(nèi)運輸完即可，二分的下限是weights的最大值，上限是weights之和
1 #1011
2 #Runtime: 400 ms (Beats 51.78%)
3 #Memory: 15.4 MB (Beats 32.99%)
4
5 class Solution(object):
6 def shipWithinDays(self, weights, days):
7 """
8 :type weights: List[int]
9 :type days: int
10 :rtype: int
11 """
12 l = max(weights)
13 r = sum(weights)
14
15 def check(cap):
16 t = 1
17 c = 0
18 for wi in weights:
19 if c + wi > cap:
20 t += 1
21 c = 0
22 c += wi
23 if t <= days:
24 return True
25 return False
26
27
28 while l < r:
29 mid = (l + r) // 2
30 if check(mid):
31 r = mid
32 else:
33 l = mid + 1
34 return r