1710.maximum-units-on-a-truck 卡车上的最大单元数

问题描述

1710.卡车上的最大单元数

解题思路

根据每个箱子可以装载的单元数量从大到小对boxTypes排序，然后每次将单元数量最大的箱子填入卡车。

使用快速选择算法可以将时间复杂度降低到\(O(n)\)。

代码

class Solution {
  public:
    int maximumUnits(vector<vector<int>> &boxTypes, int truckSize) {
        std::sort(boxTypes.begin(), boxTypes.end(), [&](vector<int> vec1, vector<int> vec2) { return vec1[1] >= vec2[1]; });
        int cnt = 0, sum = 0;
        for (int i = 0; i < boxTypes.size(); i++) {
            if (cnt + boxTypes[i][0] <= truckSize) {
                sum += boxTypes[i][0] * boxTypes[i][1];
                cnt += boxTypes[i][0];
            } else {
                sum += (truckSize - cnt) * boxTypes[i][1];
                break;
            }
        }
        return sum;
    }
};