使用大尺寸向量时出现运行时错误

Question

这是基于 Kattis 上的一个名为“银河大学编程竞赛”的问题。我尝试用 C++ 制定一个解决方案，它适用于较小的数字，例如他们的测试输入：

3 4
2 7
3 5
1 6
1 9

但是一旦我引入他们给出的更大的数字，程序就会突然在运行时卡住并且不会产生任何输出。在我包含的代码中，我还为这些大数字设置了测试用例。是否存在某种内存泄漏或类似的原因导致此问题？我该如何解决它？

经过更多测试后，该程序似乎运行时间太长，因此我的IDE将其挂起。对于大型案例（但小于我在这里提供的测试案例），它似乎运行良好，只是需要很长时间。即处理从 1 到 1000 的数字时需要 15 秒。当使用更大的数字 1 到 1000000 时，我需要将运行时间降低到 2 秒以下。所以我想我的实际问题是如何使这段代码更高效？

#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;
}

Answer 1

您面临的问题是由于 favoriteTeam 和团队之间的规模差异。 就像如果 numTeams 小于 numEvents 那么当您调整球队和 favoriteTeam 的大小时，您将拥有比球队数量更多的最喜欢球队。