c++ - spoj(歧义排列)

Question

我在 spoj 上解决了一个名为 Ambiguous Permutations(http://www.spoj.com/problems/PERMUT2/)的简单问题，当我测试小输入时它工作正常，但在提交时它显示运行时错误 - 段错误。我无法弄清楚(尽管我浪费了很多时间，并且只感到沮丧)。请帮忙。

#include <iostream>
#include <stdlib.h>
#include <string.h>

char arr1[200000];//stores original string.
char arr2[200000];//stores inverse permutation.

long int n;

using namespace std;

int main()
{
    while (1)
    {
        cin >> n;
        if (n == 0)
        {
            exit(0);
        }
        getchar();
        gets(arr1);
        //creating inverse permutation.
        for (long int i = 0; i < 2 * n - 1; i++)
        {
            if (i % 2 == 1)
            {
                arr2[i] = ' ';
            }
            else
            {
                arr2[2 * (arr1[i] - '0') - 2] = i / 2 + '1';
            }
        }
        arr2[2 * n - 1] = '\0';
        //comparing string with it's inverse permutation.
        if (strcmp(arr1, arr2) == 0)
        {
            cout << endl << "ambiguous";
        }
        else
        {
            cout << endl << "not ambiguous";
        }
    }
    return 0;

}

Answer 1

问题是您正在使用 char 数组来表示整数，并且您的代码假定每个数字都由一个 char 表示(注意例如检查 i % 2 == 1 以确定是否数字或空格)。
因此，任何大于 9 的数字都会导致正确性/内存问题。

如果您将使用整数数组，它会容易得多。

您将不再担心空格字符 ' '，不需要从单元格中递减 '0' 字符，也不需要您的循环运行到 2 * n - 1。

我认为这样更清楚:

#include <iostream>

using namespace std;

const int MAX_SIZE = 1000;

int arr1[MAX_SIZE];
int arr2[MAX_SIZE];
int size = 0;

bool areArrsEqual()
{
    for (int i = 0; i < size; ++i)
    {
        if (arr1[i] != arr2[i])
        {
            return false;
        }
    }
    return true;
}

int main()
{
    cin >> size;

    while (size > 0 && size <= MAX_SIZE)
    {
        for (int i = 0; i < size; ++i)
        {
            cin >> arr1[i];
        }

        // creating inverse permutation.
        for (int i = 0; i < size; i++)
        {
            // if (arr[i] - 1 >= size) ==> illegal input.
            arr2[arr1[i] - 1] = i + 1;
        }

        // comparing permutation with it's inverse permutation.
        if (areArrsEqual())
        {
            cout << "ambiguous" << endl;
        }
        else
        {
            cout << "not ambiguous" << endl;
        }
        cin >> size;
    }
    return 0;
}

输出:

4
1 4 3 2
ambiguous
5
2 3 4 5 1
not ambiguous
1
1
ambiguous
13
1 2 3 4 5 6 7 8 9 10 11 12 13
ambiguous
0