C++大vector场景程序运行超时问题及优化咨询

我在做Kattis平台的《Galactic Collegiate Programming Contest》题目时，C++代码在小测试用例下运行正常，但处理大数据时直接超时，IDE都会强制暂停。
小测试用例：

3 4
2 7
3 5
1 6
1 9

测试发现处理1000规模的数据需要15秒，我需要把代码优化到能在2秒内处理1000000级别的数据。附上当前实现代码，求优化方案：

#include <iostream>
#include <vector>

#include <cstdlib>
#include <ctime>

using namespace std;

struct Team
{
    int solP; // Number of solved problems
    int numP; // Number of penalties
    int rank;
};

int main()
{
    srand(time(0)); 
    vector<Team> teams; // 0 denotes team 1
    vector<int> favoriteTeam; // Filled with ranks of favorite team
    vector<int> rank; // Filled with ranks from last event
    int numTeams;
    int numEvents;

    //cin >> numTeams >> numEvents; // Read in line 1 // TEST TEST TEST
    numTeams = (rand() % (int)10e5) + 1;
    numEvents = (rand() % (int)10e5) + 1;
    teams.resize(numTeams);
    favoriteTeam.resize(numEvents);
    rank.resize(numTeams);
    for (int i = 0; i < numTeams; i++)
    {
        Team temp;
        temp.solP = 0;
        temp.numP = 0;
        temp.rank = 1;
        teams[i] = temp;
    }

    for (int i = 0; i < numEvents; i++)
    {
        int t, p;
        t = (rand() % numTeams) + 1;
        p = (rand() % 1000) + 1;
        ++teams[t - 1].solP;
        teams[t - 1].numP += p;

        // CALL FOR ORDER
        int modifier;
        int bestIndex;
        vector<bool> tie(numTeams);
        vector<bool> used(numTeams, false);

        // Sets up the rank vector
        for (int i = 0; i < numTeams; i++)
        {
            bestIndex = i;
            for (int j = 0; j < numTeams; j++)
            {
                if (i == j || used[j]) continue;
                if (used[i] || teams[j].solP > teams[bestIndex].solP || teams[j].solP == teams[bestIndex].solP && teams[j].numP <= teams[bestIndex].numP)
                {
                    bestIndex = j;
                }
            }
            rank[i] = bestIndex;
            used[bestIndex] = true;
        }

        // Sets up the tie vector
        for (int i = 0; i < numTeams; i++)
        {
            if (i != 0 && teams[rank[i]].solP == teams[rank[i - 1]].solP && teams[rank[i]].numP == teams[rank[i - 1]].numP)
            {
                tie[i] = true;
            }
            else tie[i] = false;
        }

        // Sets the rank for each team
        modifier = 0;
        for (int i = 0; i < numTeams; i++)
        {
            if (tie[i]) modifier++;
            teams[rank[i]].rank = i + 1 - modifier;
        }

        // Set output
        favoriteTeam[i] = teams[0].rank;
    }

    //cout << endl;
    for (int i = 0; i < numEvents; i++)
    {
        cout << favoriteTeam[i] << endl;

    }

    cout << clock() / (double)CLOCKS_PER_SEC << endl;

    return 0;
}

核心问题：时间复杂度爆炸 #

你当前的代码在每个事件后都用双重循环全量排序，时间复杂度是O(E*T²)（E是事件数，T是队伍数）。当E和T都达到1e5时，总运算量会达到1e10次，这远远超出了CPU每秒约1e8次运算的能力，必然超时。必须把单次更新的复杂度降到O(1)级别。

关键优化：利用"每次仅一个队伍状态变化"的特性 #

题目中每个事件只会修改一个队伍的解题数和罚时，其他队伍状态完全不变。我们不需要维护所有队伍的排名，只需要跟踪比队伍1（目标队伍）强的队伍数量，队伍1的排名就是这个数量+1。

具体逻辑 #

1. 定义"队伍X比队伍Y强"的规则：X的解题数更多，或者解题数相同但罚时更少。
2. 维护一个变量better_count，记录当前比队伍1强的队伍总数。
3. 每次处理事件时：
   • 先判断更新前，目标队伍是否比队伍1强，记录状态。
   • 更新目标队伍的解题数和罚时。
   • 再判断更新后，目标队伍是否比队伍1强。
   • 根据前后状态的变化，调整better_count：
     • 如果之前强、现在不强：better_count--
     • 如果之前不强、现在强：better_count++
     • 其他情况（状态不变）：不修改better_count
4. 队伍1的排名直接等于better_count + 1。

其他细节优化 #

1. 输入输出加速：处理百万级数据时，默认的cin/cout速度很慢，需要关闭同步：

   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   

   输出时用'\n'代替endl，因为endl会强制刷新缓冲区，大幅拖慢速度。
2. 移除冗余变量：原来的rank、tie、used等向量完全不需要，直接删除以节省内存和初始化时间。
3. 测试代码调整：实际提交时要把随机生成数据的代码换成读取cin输入，测试时可以保留rand()但注意范围（rand()的最大值可能小于1e5，如需更稳定的随机数可以用<random>库）。

优化后的完整代码 #

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

struct Team {
    int solP = 0; // 解题数
    int numP = 0; // 罚时
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    srand(time(0));
    vector<Team> teams;
    vector<int> favoriteTeam;
    int numTeams, numEvents;

    // 测试用随机数据，提交时替换为 cin >> numTeams >> numEvents;
    numTeams = (rand() % 100000) + 1;
    numEvents = (rand() % 100000) + 1;

    teams.resize(numTeams);
    favoriteTeam.resize(numEvents);

    int better_count = 0; // 比队伍1强的数量

    for (int i = 0; i < numEvents; ++i) {
        int t, p;
        // 测试用随机数据，提交时替换为 cin >> t >> p;
        t = (rand() % numTeams) + 1;
        p = (rand() % 1000) + 1;

        Team& target = teams[t - 1];
        Team& fav = teams[0];

        // 记录更新前是否比队伍1强
        bool was_better = false;
        if (target.solP > fav.solP || (target.solP == fav.solP && target.numP < fav.numP)) {
            was_better = true;
        }

        // 更新目标队伍状态
        target.solP++;
        target.numP += p;

        // 记录更新后是否比队伍1强
        bool is_better = false;
        if (target.solP > fav.solP || (target.solP == fav.solP && target.numP < fav.numP)) {
            is_better = true;
        }

        // 更新计数
        if (was_better && !is_better) {
            better_count--;
        } else if (!was_better && is_better) {
            better_count++;
        }

        // 记录队伍1的排名
        favoriteTeam[i] = better_count + 1;
    }

    // 输出结果
    for (int r : favoriteTeam) {
        cout << r << '\n';
    }

    cout << clock() / (double)CLOCKS_PER_SEC << '\n';
    return 0;
}

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