装满石头的背包的最大数量

输入：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 这个结果。

输入：capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100 输出：3 解释： 8 块石头放入背包 0 ，2 块石头放入背包 2 。每个背包中的石头总数是 [10,2,2] 。背包 0 、背包 1 和背包 2 都装满石头。总计 3 个背包装满石头，所以返回 3 。可以证明不存在超过 3 个背包装满石头的情况。注意，不必用完所有的额外石头。

1
2
3
4
5
6
class Solution {
public:
    int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
        
    }
};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

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

}

/**

* 对每个背包所差石头数排序，从小到大一个一个填满，所需石头大于所给石头就说明此背包已经填不满，之前的均已填满

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;

}

详情