Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出所有货物的重量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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理