竞赛编程算法疑问：为何高复杂度实现未超时反而通过测试？

我为一道竞赛编程题实现了两种算法，第一种出现了TLE（超时），但第二种虽然在循环内使用erase方法（理论时间复杂度更高），却被判定为正确答案（AC）。请解释第二种实现比第一种更快的原因，重点关注while(true)循环内的第一个if语句。

第一种实现（TLE） #

bool isEmpty (vector<int> a) {
    sort(a.begin(), a.end());
    
    return a.size() == 0 || a[a.size() - 1] == 0;
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int m, n, l;
    cin>>n>>l;
    
    vector<int> k;
    vector<int> q;
    
    for (int i=0; i<n; i++){
        int ki;
        cin>>ki;
        k.push_back(ki);
    }
    
    cin>>m;
    
    for (int i=0; i<m; i++){
        int qi;
        cin>>qi;
        q.push_back(qi);
    }
    
    vector<int> bagsNeeded;
    
    for (int qi:q){
        if (qi % l == 0){
            bagsNeeded.push_back(qi / l);
        }
        else {
            bagsNeeded.push_back((qi / l) + 1);
        }
    }
    
    sort(bagsNeeded.begin(), bagsNeeded.end());
    int i = 0;
    int c = 0;
    while(true){
        auto itr = lower_bound(bagsNeeded.begin(), bagsNeeded.end(), k[i]);

        // Difference between the two implementations is inside this if statement
        if (itr == bagsNeeded.end()){
            if (isEmpty(bagsNeeded)) break;
            else {
                int bags = k[i];
                int carriable = 0;
                int j = bagsNeeded.size() - 1;
                c++;
                while(bags > 0 && j >= 0){
                    if (bagsNeeded[j] <= bags){
                        bags -= bagsNeeded[j];
                        bagsNeeded[j] = 0;
                    }
                    else {
                        bagsNeeded[j] -= bags;
                        bags = 0;
                    }
                    j--;
                }
            }
        }
        else if (itr == bagsNeeded.begin()){
            bagsNeeded[0] -= k[i];
            if (bagsNeeded[0] == 0){
                bagsNeeded.erase(itr);
            }
            c++;
        }
        else {
            bagsNeeded[itr - bagsNeeded.begin()] -= k[i];
            if (bagsNeeded[itr - bagsNeeded.begin()] == 0){
                bagsNeeded.erase(itr);
            }
            c++;
        }
        i++;
        if (i == n){
            i = 0;
        }
    }
    cout<<c<<"\n";
    return 0;
}

第二种实现（AC） #

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int m, n, l;
    cin>>n>>l;
    
    vector<int> k;
    vector<int> q;
    
    for (int i=0; i<n; i++){
        int ki;
        cin>>ki;
        k.push_back(ki);
    }
    
    cin>>m;
    
    for (int i=0; i<m; i++){
        int qi;
        cin>>qi;
        q.push_back(qi);
    }
    
    vector<int> bagsNeeded;
    
    for (int qi:q){
        if (qi % l == 0){
            bagsNeeded.push_back(qi / l);
        }
        else {
            bagsNeeded.push_back((qi / l) + 1);
        }
    }
    
    sort(bagsNeeded.begin(), bagsNeeded.end());
    int i = 0;
    int c = 0;
    while(true){
        auto itr = lower_bound(bagsNeeded.begin(), bagsNeeded.end(), k[i]);
        if (itr == bagsNeeded.end()){
            if (bagsNeeded.size() == 0) break;
            else {
                int bags = k[i];
                int carriable = 0;
                int j = bagsNeeded.size() - 1;
                c++;
                while(bags > 0 && j >= 0){
                    if (bagsNeeded[j] <= bags){
                        bags -= bagsNeeded[j];
                        bagsNeeded.erase(bagsNeeded.begin() + j);
                    }
                    else {
                        bagsNeeded[j] -= bags;
                        bags = 0;
                    }
                    j--;
                }
            }
        }
        else if (itr == bagsNeeded.begin()){
            bagsNeeded[0] -= k[i];
            if (bagsNeeded[0] == 0){
                bagsNeeded.erase(itr);
            }
            c++;
        }
        else {
            bagsNeeded[itr - bagsNeeded.begin()] -= k[i];
            if (bagsNeeded[itr - bagsNeeded.begin()] == 0){
                bagsNeeded.erase(itr);
            }
            c++;
        }
        i++;
        if (i == n){
            i = 0;
        }
    }
    cout<<c<<"\n";
    return 0;
}

核心原因分析 #

1. isEmpty函数的致命性能开销

第一种实现中的isEmpty函数是TLE的核心原因：

• 每次调用都会复制整个bagsNeeded向量，产生O(m)的时间和内存开销（m为当前向量大小）；
• 随后还要对副本进行排序，时间复杂度O(m log m)；
• 当bagsNeeded中留存大量0元素时，这个函数会被反复调用，每次都要执行上述高开销操作，直接拖垮整体性能。

2. 无效元素累积导致后续操作效率暴跌

第一种实现处理大承载量的k[i]时，只是将能装下的bagsNeeded[j]设为0，而非直接删除：

• 这会让bagsNeeded中堆积大量无效的0元素，后续的lower_bound查找、循环遍历都要遍历这些无效元素，增加了不必要的计算量；
• 比如lower_bound原本只需要处理有效元素，现在要遍历包含大量0的数组，每次查找的时间成本显著上升。

3. erase操作反而降低了总计算量

第二种实现用erase直接删除已处理完的元素，看似单次erase是O(m)复杂度，但带来了两个关键优化：

• 向量快速缩小：删除元素后，bagsNeeded的大小会快速递减，后续所有依赖向量大小的操作（lower_bound、遍历）的次数都会大幅减少；
• 无无效元素干扰：向量中始终只有有效元素，避免了第一种实现中对0元素的无效处理，整体总运算量反而远低于第一种。

4. 循环终止条件的高效判断

第二种实现直接用bagsNeeded.size() == 0判断终止，这是O(1)的操作；而第一种的isEmpty是O(m log m)的高开销操作，在循环后期会被频繁触发，成为主要耗时点。

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