Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
有一些包,每个里面已经装了rocks[i]的物品,每个包容量capacity[i],现在还有additionalRocks重量的物品,问最多可以有几个包被装满,贪心

计算每个包剩余容量,并且从小到大排序,一个个装直到包全部装满或者additionalRocks用完即可

 1 #2279
 2 #Runtime: 836 ms (Beats 86.21%)
 3 #Memory: 20.2 MB (Beats 93.10%)
 4 
 5 class Solution(object):
 6     def maximumBags(self, capacity, rocks, additionalRocks):
 7         """
 8         :type capacity: List[int]
 9         :type rocks: List[int]
10         :type additionalRocks: int
11         :rtype: int
12         """
13         for i in range(len(capacity)):
14             capacity[i] = max(capacity[i] - rocks[i], 0)
15         capacity.sort()
16         for i in range(len(capacity)):
17             additionalRocks -= capacity[i]
18             if additionalRocks < 0:
19                 i -= 1
20                 break
21         return i + 1

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