C++矢量和记忆运行时错误问题

Question

我在 Codechef 此处遇到了问题。我正在尝试使用向量进行记忆。由于我对编程还是个新手，而且对 STL 容器也不太熟悉，所以我使用了 vector 作为查找表。 （尽管，有人建议我使用 map 有助于解决问题）。

所以，我的问题是下面给出的解决方案如何遇到运行时错误。为了得到错误，我使用问题的边界值 (100000000) 作为输入。我的 Netbeans IDE 显示的错误消息是 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 == 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 mb 的内存。

我不知道你正在解决哪个问题，但看起来你正在解决 Bytelandian 硬币。为此，最好使用映射，因为：

1. 您通常不会在测试用例运行中存储所有 100000000 个用例的值。因此，您需要一种只为您实际记忆的值分配内存的方法。
2. 即使是，您也不需要持续时间查找。尽管 std::map 会加快程序速度，但它使用树来为您提供对数查找时间。它消除了连续使用 762 mb 的要求。 762 mb 不是什么大问题，但在单个块中的预期却是大问题。

因此，在您的情况下最好使用的是 std::map。在您的情况下，实际上只需将 std::vector 替换为 std::map 就可以作为 map 还具有 [] 操作员访问权限 [在大多数情况下，它应该]。