有一些包,每个里面已经装了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