歧义排列问题代码:PERMUT2(codechef)

问题描述 投票:-1回答:1

检查模棱两可的排列

输入:输入包含几个测试用例。每个测试用例的第一行包含一个整数n(1≤n≤100000)。然后在下一行中对整数1到n进行排列。连续整数之间只有一个空格字符。您可以假设1到n之间的每个整数在排列中恰好出现一次。最后一个测试用例后跟零。

输出:对于每个测试用例输出,排列是否模棱两可。遵循示例输出中显示的格式。

我的输出仍然正确,但是代码在提交时返回错误的答案。不确定出什么问题。


int main(void) {
    int n, i, c, d;
    while(scanf("%d", &n), n!=0){
        c=0;
        int a[n];
        for(i=0; i<n; i++){
        scanf("%ld", &a[i]);
        c=c*10+a[i];
        }
        i=n;
        int b[n];
        while(i>0){
            b[a[i-1]-1]=i;
            --i;
        }
        d=0;
        for(i=0; i<n; i++){
            d=d*10+b[i];
        }
        c==d ? printf("ambiguous\n") : printf("not ambiguous\n");
    }
    return 0;
}
c algorithm
1个回答
0
投票

我了解您的思考过程,排列表示的和与逆排列表示的和应该相同,但是并非在所有情况下都是正确的,因为可能存在一些排列,它们的总和相等但不相同模棱两可。

一种更简单,更鲁棒的方法是检查每个排列元素是否与逆排列相匹配

通过下面的代码,该代码在Codechef上处于接受状态:

#include<stdio.h>

int main(void) {
int n, i;
while(scanf("%d", &n), n!=0){

    int a[n];
    for(i=0; i<n; i++){
        scanf("%d", &a[i]);
    }
    i=n;
    int b[n];
    while(i>0){
        b[a[i-1]-1]=i;
        --i;
    }

    int flg = 1;

    for(int i=0;i<n;i++){
        if(a[i]!=b[i]){
            flg = 0;
            break;
        }
    }
    (flg==1) ? printf("ambiguous\n") : printf("not ambiguous\n");
}
return 0;

}

请随时提出任何疑问。

© www.soinside.com 2019 - 2024. All rights reserved.