全排列的变换

柔光的暖阳◎ 2022-05-16 12:06 44阅读 0赞

Problem Description  
小鑫今天从玄黄那里拿到了一个长度为n的全排列，可是小鑫不喜欢这个全排列，于是小鑫想要把这个全排列变成他希望的样子。

但是全排列不是随便就能变换的，全排列每次变换只能交换相邻的两个数位。例如：123可以通过一步变换变成132，但是不能通过一步变换变成321。

现在你能帮助小鑫把他从玄黄那里拿到的全排列变成他希望的样子吗？小鑫想知道最少需要多少步变换才能将手里的全排列变成他希望的样子。

Input  
第一行输入一个整数n（3<=n<=9），代表全排列的长度。

第二行输入一个长度为n的全排列，相邻两个数字之间用空格隔开，代表这是小鑫开始获得的全排列。

第三行输入一个长度为n的全排列，相邻两个数字之间用空格隔开，代表小鑫希望获得的全排列。

Output  
输出一个整数，代表从第一个全排列变成第二个全排列最少需要进行的变换次数。

Sample Input  
4  
1 2 4 3  
3 2 1 4  
Sample Output  
4  
Hint  
第一步，将1和2交换变为2 1 4 3

第二步，将4和3交换变为2 1 3 4

第三步，将1和3交换变为2 3 1 4

第四步，将2和3交换变为3 2 1 4  
分析：这个题我们可以用a数组去存放，真正位置的序号，也就是a存放本来该有的位置，然后通过冒泡排序记录交换的次数。这种方法值得用。  
接下来直接看代码：

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
        int n,a[100],b[100],i,j,t,sum=0;
        scanf("%d",&n);
        for(i=0;i<=n-1;i++)
        {
            scanf("%d",&a[i]);
        }
        for(i=0;i<=n-1;i++)
        {
            scanf("%d",&b[i]);
        }
        for(i=0;i<=n-1;i++)
        {
            for(j=0;j<=n-1;j++)
            {
                if(a[i]==b[j])
                {
                    a[i]=j;
                    break;
                }
            }
        }
        for(i=0;i<=n-2;i++)
        {
            for(j=0;j<=n-2-i;j++)
            {
                if(a[j]>a[j+1])
                {
                    t=a[j];a[j]=a[j+1];a[j+1]=t;
                    sum++;
                }
            }
        }
        printf("%d\n",sum);
        return 0;
    }

中间的break;必须写。