class Solution {
public:
int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
}
};
2279. 装满石头的背包的最大数量
现有编号从 0 到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。另给你一个整数 additionalRocks ，表示你可以放置的额外石头数量，石头可以往 任意 背包中放置。
请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的 最大 数量。
示例 1：
输入：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2 输出：3 解释： 1 块石头放入背包 0 ，1 块石头放入背包 1 。 每个背包中的石头总数是 [2,3,4,4] 。 背包 0 、背包 1 和 背包 2 都装满石头。 总计 3 个背包装满石头，所以返回 3 。 可以证明不存在超过 3 个背包装满石头的情况。 注意，可能存在其他放置石头的方案同样能够得到 3 这个结果。
示例 2：
输入：capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100 输出：3 解释： 8 块石头放入背包 0 ，2 块石头放入背包 2 。 每个背包中的石头总数是 [10,2,2] 。 背包 0 、背包 1 和背包 2 都装满石头。 总计 3 个背包装满石头，所以返回 3 。 可以证明不存在超过 3 个背包装满石头的情况。 注意，不必用完所有的额外石头。
提示：
n == capacity.length == rocks.length1 <= n <= 5 * 1041 <= capacity[i] <= 1090 <= rocks[i] <= capacity[i]1 <= additionalRocks <= 109原站题解
python3 解法, 执行用时: 148 ms, 内存消耗: 22.1 MB, 提交时间: 2022-11-27 11:41:53
class Solution:
def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
n = len(capacity)
rest = [0] * n
for i in range(n):
rest[i] = capacity[i] - rocks[i]
rest.sort()
ans = 0
i = 0
while additionalRocks > 0 and i < n:
if rest[i] <= additionalRocks:
additionalRocks -= rest[i]
ans += 1
i += 1
return ans
golang 解法, 执行用时: 136 ms, 内存消耗: 7.9 MB, 提交时间: 2022-11-27 11:41:25
func maximumBags(capacity, rocks []int, additionalRocks int) (ans int) {
for i := range capacity {
capacity[i] -= rocks[i]
}
sort.Ints(capacity) // 先装剩余最小的
for _, leftSpace := range capacity {
if leftSpace > additionalRocks { // 无法装满，那后续也无法装满（因为排序了）
break // 直接退出
}
ans++
additionalRocks -= leftSpace
}
return
}
java 解法, 执行用时: 13 ms, 内存消耗: 52.7 MB, 提交时间: 2022-11-27 11:41:09
/**
* 对每个背包所差石头数排序，从小到大一个一个填满，所需石头大于所给石头就说明此背包已经填不满，之前的均已填满
*/
class Solution {
public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
int[] arr = new int[capacity.length];
for (int i = 0; i < capacity.length; i++) {
arr[i] = capacity[i]-rocks[i];
}
Arrays.sort(arr);
int num=0;
int i ;
for ( i =1; i <= capacity.length; i++) {
num+=arr[i-1];
if (num>additionalRocks){
return i-1;
}
}
return i-1;
}
}