题目简介：
请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：
numberOfBoxesi 是类型 i 的箱子的数量。numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。
整数 truckSize 表示卡车上可以装载 箱子 的 最大数量 。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。
返回卡车可以装载 单元 的 最大 总数。
示例 1：
1
2
3
4
5
6
7
8
| 输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
输出：8
解释：箱子的情况如下：
- 1 个第一类的箱子，里面含 3 个单元。
- 2 个第二类的箱子，每个里面含 2 个单元。
- 3 个第三类的箱子，每个里面含 1 个单元。
可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。
单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8
|
提示：
1 <= boxTypes.length <= 10001 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 10001 <= truckSize <= 10^6
思路：
贪心，排序后依次选择最大的即可。需要注意的是箱子可能会全被选完。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
sort(boxTypes.begin(), boxTypes.end(), [](vector<int>& a, vector<int>& b){
return a[1] > b[1];
});
int res = 0;
int i = 0;
while(i < boxTypes.size()){
if(truckSize <= boxTypes[i][0]){
res += truckSize * boxTypes[i][1];
break;
}
res += boxTypes[i][0] * boxTypes[i][1];
truckSize -= boxTypes[i][0];
i++;
}
return res;
}
};
|
