LeetCode卡车上的最大单元数C++代码输出不符问题排查

正在求解LeetCode题目《卡车上的最大单元数》，题目链接。已知晓该题正确解法，需要定位当前编写代码的逻辑问题，相关测试用例如下。

class Solution {
public:
    static bool comparator(vector<int>&a,vector<int>&b){
        return a[1]>b[1];
    }
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        
        sort(boxTypes.begin(),boxTypes.end(),comparator);
        int sum=0;

        for(int i =0;i<boxTypes.size();i++){
           
            if(truckSize>boxTypes[i][0]){
                sum+=boxTypes[i][0] * boxTypes[i][1];
                truckSize= truckSize - boxTypes[i][0];
                
            }else{
                sum += truckSize * boxTypes[i][1];
                
            }
            
        }
        return sum;
    }
};

测试用例 #

用例1：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
用例2：boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10

预期输出 #

8
91

实际运行输出 #

8
101

第一个测试用例运行结果符合预期，第二个测试用例输出值与预期不符。

错误出现在卡车装满后的处理逻辑：
当进入else分支时，说明当前类型箱子的数量大于剩余卡车容量，此时已经取truckSize数量的箱子把卡车装满，但代码既没有终止遍历，也没有将剩余容量truckSize置为0，导致循环会继续遍历后续所有箱子类型，重复累加truckSize * 对应单元数，最终计算的总单元数偏大。

以第二个测试用例为例：

• 按单元数降序排序后的箱子顺序为：[5,10]、[3,9]、[4,7]、[2,5]
• 遍历到[5,10]：剩余容量10>5，累加5*10=50，剩余容量变为5
• 遍历到[3,9]：剩余容量5>3，累加3*9=27，剩余容量变为2
• 遍历到[4,7]：剩余容量2<4，累加2*7=14，此时总和为91，卡车已经装满，但代码没有退出循环
• 遍历到[2,5]：仍然进入else分支，累加2*5=10，总和变为101，和错误输出完全一致。

在else分支计算完最后一批装载的单元数后，直接加break终止循环即可，因为卡车已经装满，不需要再遍历后续箱子：

else{
    sum += truckSize * boxTypes[i][1];
    break;
}

也可以在else分支将truckSize置为0，后续循环累加的数值都是0，不会影响最终结果，但是加break的执行效率更高。

内容的提问来源于stack exchange，提问作者Manishyadav