HihoCoder - 1691 数字游戏 （全排列函数）

小Hi和小Ho在玩一个数字游戏。

小Hi给出两个N位整数A和B(可能有前导0)，小Ho需要经过最少次数的变换将A变成B。

一次变换可以进行以下操作之一：

1. 交换任意两位数字。例如 12345 -> 42315。  

2. 选择任意一位数字加1或减1。注意0减1会变成9，9加1会变成0。  

请你帮助小Ho求出最少的变换次数。

Input

第一行包含一个整数N，代表位数。  

第二行包含两个整数A和B。  

对于50%的数据，1 ≤ N ≤ 6  

对于100%的数据，1 ≤ N ≤ 10， A和B都是N位整数(可能有前导0)。

Output

一个整数，代表最少的变换次数。

Sample Input

4  
1234 4391      

Sample Output

5      

这道题要用到全排列函数next_permutation，它的作用是自动生成一个全排列。

原序列为a，目标序列为b，那么我们可以知道因为二操作的存在，无论如何我们都能把a变成b，从而我们能得到最优解。

全排列函数使用的目的就是为了让a数组中的数字进行全排列实现所有的情况，然后我们通过所有的情况去对照目标数组b来找到最优解。虽然这种暴力的思想很简单，但是代码不好懂。并且实现第一个操作有个大问题，我们要交换数组中两个数，交换的前提是我们通过a与b的对比在目标数组中找到了a重元素应该在的位置，然后进行交换，因为使用全排列函数，a重元素顺序要打乱，我们要用其他数组来记录位置，那么在实现交换元素时会出错，我们还要在一开始统计下标，来当做编号。代码有详细注释

下标：i：0 1 2 3

起始 a[]:  1 2 3 4

目标 b[]:  4 3 9 1

编号 bh：0 1 2 3

        x[]:  0 1 2 3(用来记录每次全排列后的元素)

    pos[]:  0 1 2 3(用来记录x的下标）

我们在进行操作是其实是一直对a数组中的元素编号进行操作，当我们动了bh，那么我们就是动了a数组的编号，间接地对a数组进行了操作。现在还有一个问题，我们全排列后的数组已经改变了原来数组的位置，我们拿着改变后的数组去比较目标数组会不会有错？再看之前说的，我们肯定能得到交换次序，因为我们改变的是编号，我们可以通过编号来找相对应的数组，那么已经改变过的序列我们也可以用编号来找到对应的数，然后进行加减操作也能变成目标序列。因为全排列罗列了所有情况，那么我们就可以暴力枚举所有情况找最优解。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
char a[50],b[50];
int bh[50],pos[50],x[50];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        scanf("%s%s",a,b);
        for(int i=0;i<n;i++)
            bh[i]=i;//记录编号，对a数组的下标记录，这样的话就避免了重复元素的出现实现了每个元素一个编号
        int minn=inf,cnt;//minn用来记录次数最少，就是答案，cnt用来统计每次全排列过程中的次数
        do
        {
            cnt=0;
            for(int i=0;i<n;i++)
            {
                x[i]=bh[i];//在这里先说明一点，bh数组记录了a，b数组中的每个元素的编号，而b数组是目标数组我们不用动它
//当我们更改了bh数组也就是说我们更改了a数组。x数组用来记录全排列后的a数组的编号               
                pos[x[i]]=i;//记录位置
            }
            for(int i=0;i<n;i++)
            {
                if(x[i]!=i)//前边提到我们一直都是在更改编号，由于b数组没动过，那么编号仍然是下边i，而经过我们操作后的x数组记录的则是操作后的
//a数组元素编号，原来a，b的元素编号是一样的，那么现在只要a数组的元素编号在i相同的情况下与b元素编号不同就代表改变了位置                    
                {
                    pos[x[i]]=pos[i];//更改编号代表
                    swap(x[i],x[pos[i]]);
                    cnt++;
                }
            }
            for(int i=0;i<n;i++)//计算交换次数后，计算加减1的次数。
            {
                cnt+=min(abs(a[bh[i]]-b[i]),10-abs(a[bh[i]]-b[i]));
            }
            minn=min(minn,cnt);
        }while(next_permutation(bh,bh+n));
        printf("%d\n",minn);
    }
}