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);
    }
}