题目描述
请你将一些箱子装在 一辆卡车 上。给定一个二维数组 boxTypes
,其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]
:
numberOfBoxes_i
是类型i
的箱子的数量。numberOfUnitsPerBox_i
是类型i
每个箱子可以装载的单元数量。
整数 truckSize
表示卡车上可以装载 箱子 的 最大数量。只要箱子数量不超过 truckSize
,你就可以选择任意箱子装到卡车上。
返回卡车可以装载 单元 的 最大 总数。
样例
输入:boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
输出:8
解释:箱子的情况如下:
- 1 个第一类的箱子,里面含 3 个单元。
- 2 个第二类的箱子,每个里面含 2 个单元。
- 3 个第三类的箱子,每个里面含 1 个单元。
可以选择第一类和第二类的所有箱子,以及第三类的一个箱子。
单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8
输入:boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
输出:91
限制
1 <= boxTypes.length <= 1000
1 <= numberOfBoxes_i, numberOfUnitsPerBox_i <= 1000
1 <= truckSize <= 10^6
算法
(贪心,排序) $O(n \log n)$
- 将箱子按照可装载的单元数量从大到小排序,依次装上卡车,直到不能再装下为止。
时间复杂度
- 排序的时间复杂度为 $O(n \log n)$。
- 排序后统计答案时间复杂度为 $O(n)$。
- 故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
sort(boxTypes.begin(), boxTypes.end(), [](const vector<int> &x, const vector<int> &y) {
return x[1] > y[1];
});
int tot = 0, ans = 0;
for (const auto &b : boxTypes)
if (tot + b[0] <= truckSize) {
tot += b[0];
ans += b[0] * b[1];
} else {
ans += (truckSize - tot) * b[1];
break;
}
return ans;
}
};
第一眼看还以为是多重背包,然后发现数据范围有点奇怪😅