Ошибка времени выполнения c ++ при использовании векторов push и итератора - PullRequest
Новая
       20

Ошибка времени выполнения c ++ при использовании векторов push и итератора

0 голосов
/ 28 сентября 2018

Привет! Я пытаюсь решить проблему с алгоритмом, и когда я отправляю свой код в онлайн-судью, я продолжаю получать ошибку во время выполнения.Я понятия не имею, почему это происходит.Вот проблема, которую я пытаюсь решить.problemproblem

Код выглядит следующим образом.Он отлично работает для ввода и вывода сэмплов в visual studio.Я еще не встречал входы и выходы, которые не работают должным образом или фактически встречают ошибку времени выполнения.Только онлайн-судья дает ошибку времени выполнения, поэтому я не могу понять, почему.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    int m;
    int c1;
    int c2;
    cin >> n >> m >> c1 >> c2;
    vector<int> p = {};
    vector<int> q = {};
    for (int i = 0; i < n; ++i)
    {
        int temp;
        cin >> temp;
        p.push_back(temp);
    }
    for (int i = 0; i < m; ++i)
    {
        int temp;
        cin >> temp;
        q.push_back(temp);
    }
    vector<int> distance = {};
    for (int i = 0; i < p.size(); ++i)
    {
        for (int j = 0; j < q.size(); ++j)
        {
            distance.push_back(abs(p[i] - q[j]) + abs(c1 - c2));
        }
    }
    sort(distance.begin(), distance.end());
    int min = distance[0];
    int count = 0;;
    for (int i = 0; i < static_cast<int>(distance.size()); ++i)
    {
        if (distance[0] == distance[i])
            count++;
        else
            break;
    }
    cout << min << " " << count << endl;
    return 0;
}

1 Ответ

0 голосов
/ 28 сентября 2018

Если n и m являются максимально допустимым значением 500,000, тогда расстояние будет иметь 500,000 * 500,000 элементов, которые будут использовать 1 ТБ памяти.Из-за растущего вектора, когда вы push_back, вам может понадобиться всего около 2 ТБ памяти.Он-лайн судья, по-видимому, не позволяет вам использовать столько памяти.

Если вы переосмыслите свой алгоритм, чтобы он не сохранял значения расстояния, он, вероятно, сработает.

Вы должны всегда использовать reserve on std::vector если вы знаете размер заранее, так как он должен заставить вектор выделять точно нужный объем памяти и избегать копирования в новые блоки памяти по мере роста вектора.

...