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

Raphael Liu Lv10

现有编号从 0n - 1n 个背包。给你两个下标从 0 开始的整数数组 capacityrocks 。第
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.length
  • 1 <= n <= 5 * 104
  • 1 <= capacity[i] <= 109
  • 0 <= rocks[i] <= capacity[i]
  • 1 <= additionalRocks <= 109

Problem: 2279. 装满石头的背包的最大数量

[TOC]

思路

把需要补充的石头先按序排列,再按序补充石头,直到补满或者石头不足

解题方法

先创建一个数组存放每个背包的需求,然后将这个数组按升序排列,最后再一个一个从需求少的补充,直到补满或者石头不足

Code

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
int n=capacity.length;
int[] a=new int[n];
for(int i=0;i<n;i++){
a[i]=capacity[i]-rocks[i];
}
Arrays.sort(a);//升序排列
int num=0;//次数
for(int i=0;i<n;i++){
if(a[i]<=additionalRocks){
num++;
additionalRocks-=a[i];
}else
break;
}
return num;
}
}
 Comments
On this page
2279-装满石头的背包的最大数量