(暴力+全排列)-CodeForces 814B-An express train to reveries

朱雀 2022-05-15 22:46 212阅读 0赞

*  # (暴力+全排列)-CodeForces 814B-An express train to reveries #

--------------------

*  ## **题目链接：[B. An express train to reveries][]** ##
 *  ## **思路：** ##

**题目大意是，给定n表示数组长度，还有两个数组a，b。a，b对应下标元素至少存在一个不同，求一个长度n数列，数列的元素为1~n且不能重复，并且与a，b分别有一个对应元素不同。**

易得a，b数组可能存在两种情况

**①a，b只有一个元素不同**  **②a，b有两个元素不相同**

因为所得数值各元素必须在1~n且不能重复，所以 **a和b对应下标的元素相同的仍然是所求数组的对应下标下元素**

同时记录下这些已经出现过的元素

然后**把未出现的元素将填进该数组，直到符合要求：与 a，b分别有一个对应元素不同**

所以把这些没有出现的元素进行全排列，相应填入那些a，b元素不相同的位置

*  ## **代码：** ##

#include<iostream>
    using namespace std;
    #define MAXSIZE 1005
    
    int a[MAXSIZE],b[MAXSIZE],Temp[MAXSIZE];
    int Vis[MAXSIZE]={0};   //记录出现过的元素
    int Diff_Index[MAXSIZE];  //保存a，b 中元素不相同的坐标
    int num[MAXSIZE];    //没有出现过的元素数组
    int Pailie[MAXSIZE];   //全排列结果
    int Diff_num=0;
    int n1;     //a，b长度
    int Ok=0;
    
    void Judge(int n,int Cur)   //求排列并判定
    {
        if(n==Cur&&Ok==0)   //如果Ok=1表示有符合要求的排列结果
        {
            int num1=0,num2=0;
            for(int i=0;i<n;i++)
                Temp[Diff_Index[i]]=Pailie[i];   //对应元素填入a数组与b数组不相同的下标
            for(int i=0;i<n1;i++)
            {
                if(Temp[i]!=a[i])
                    num1++;
                if(Temp[i]!=b[i])
                    num2++;
            }
            if(num1==1&&num2==1)        //各有一个不相同
                Ok=1;
        }
        else
        {
            for(int i=0;i<n;i++)
            {
                int flag=1;
                for(int j=0;j<Cur;j++)
                    if(num[j]==Pailie[i])
                        flag=0;
                if(flag)
                {
                    Pailie[Cur]=num[i];
                    Judge(n,Cur+1);
                }
            }
        }
    }
    int main()
    {
        cin>>n1;
        for(int i=0;i<n1;i++)
        {
            cin>>a[i];
            Temp[i]=a[i];  //对a进行备份
        }
        for(int i=0;i<n1;i++)
        {
            cin>>b[i];
            if(a[i]==b[i])
                Vis[a[i]]=1;   //出现过的元素
            else
                Diff_Index[Diff_num++]=i;   //保存元素不相同的坐标
        }
        int j=0;
        for(int i=1;i<=n1;i++)
        {
            if(Vis[i]==0)        
                num[j++]=i;            //保存没出现过的元素
        }
        Judge(Diff_num,0);
        for(int i=0;i<n1;i++)   //输出结果
            cout<<Temp[i]<<" ";
        cout<<endl;
        return 0;
    }

*  ## **皮一下：** ##

**我一开始根本不知道只有两种情况，所以，我用了全排列把不相同的元素进行穷举再判定，嘻嘻，真香。**

[B. An express train to reveries]: http://codeforces.com/problemset/problem/814/B