给出所有货物的重量weights,以及需要在days天内运输完,求运载量最少需要多少,运输货物需要按weights顺序进行
因为货物的传输是确定顺序的所以比较简单,二分答案,每次判断是否能在days天内运输完即可,二分的下限是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