Проблемы с вектором C ++ и ошибками выполнения памятки

Question

Я столкнулся с проблемой здесь в Codechef. Я пытаюсь использовать вектор для запоминания. Поскольку я все еще новичок в программировании и совершенно незнаком с контейнерами STL, я использовал vector для таблицы поиска. (хотя мне предложили, что использование map помогает решить проблему).

Итак, мой вопрос: как приведенное ниже решение приводит к ошибке времени выполнения? Чтобы получить ошибку, я использовал граничное значение для задачи (100000000) в качестве входных данных. Сообщение об ошибке, отображаемое в моей среде IDE Netbeans, равно RUN FAILED (exit value 1, total time: 4s) со значением 1000000000. Вот код:

#include <iostream>
#include <cstdlib>
#include <vector>
#include <string>

#define LCM 12
#define MAXSIZE 100000000
using namespace std;
/*
 * 
 */
vector<unsigned long> lookup(MAXSIZE,0);

int solve(int n)
{
    if ( n < 12) {
        return n;
    }
    else {
        if (n < MAXSIZE)  {
            if (lookup[n] != 0) {
                return lookup[n];
            }
        }

            int temp = solve(n/2)+solve(n/3)+solve(n/4);
            if (temp >= lookup[n] ) {
                lookup[n] = temp;
            }
            return lookup[n];

    }
}
int main(int argc, char** argv) {
    int t;
    cin>>t;
    int n;
    n = solve(t);
    if ( t >= n) {
        cout<<t<<endl;
    }
    else {
        cout<<n<<endl;
    }
    return 0;
}

Answer 1

Я сомневаюсь, что это проблема с памятью, потому что он уже сказал, что программа действительно работает, и он вводит 100000000.

Одна вещь, которую я заметил, в условии if вы выполняете поиск [n], даже если n == MAXSIZE (в этом точном состоянии). Поскольку C ++ использует 0-индексированные векторы, это будет 1 за концом вектора.

    if (n < MAXSIZE)  {
     ...
    }

        ...
        if (temp >= lookup[n] ) {
            lookup[n] = temp;
        }
        return lookup[n];

Я не могу догадаться, что делает алгоритм, но я думаю, что закрывающая скобка} первого "if" должна быть ниже, и вы могли бы вернуть ошибку в этом граничном условии.

Answer 2

Вам либо недостаточно памяти, либо недостаточно непрерывного адресного пространства для хранения 100 000 000 unsigned long с.

Answer 3

Это в основном проблема с памятью. Для вектора вам нужно непрерывное выделение памяти [чтобы он мог не отставать от своего обещания поиска в постоянном времени]. В вашем случае, с 8-байтовым двойным числом, вы в основном запрашиваете у вашей машины выделить около 762 МБ памяти в одном блоке.

Я не знаю, какую проблему вы решаете, но похоже, что вы решаете байтландские монеты. Для этого гораздо лучше использовать карту, потому что:

1. Вы не будете хранить значения для всех 100000000 случаев при выполнении тестового набора. Итак, вам нужен способ выделить память только для тех значений, которые вы на самом деле запоминаете.
2. Даже если это так, вам не нужен постоянный поиск по времени. Хотя это ускорило бы вашу программу, std :: map использует деревья, чтобы дать вам логарифмическое время поиска. И это устраняет необходимость использования 762 МБ непрерывно. 762 мегабайта это не большое дело, но ожидание в одном блоке составляет

Итак, лучшее, что можно использовать в вашей ситуации - это std :: map. В вашем случае, на самом деле просто замена std::vector<unsigned long> на std::map<int, unsigned long> будет работать, так как map также имеет [] операторский доступ [по большей части, он должен].