1586 - 數字排列

時間限制：1秒記憶體限制：128兆

91 次送出 36 次通過

題目描述

現有n個k位的數字，你的任務是重新安排數字每一位的位置，使得重新安排後這n個數字中最大的數字和最小的數字之差的絕對值最小，對于每一位的調整是相對于所有的數字的，例如有3個數字1234、4321和7890，重新安排的方案是交換第二位和第三位，則3個數字變為1324、4231和7980。

輸入

輸入包括多組樣例，每組樣例包括多行。每組樣例的第一行包括2個整數n和k，分别代表數字的個數和位數（1 ≤ n, k ≤ 8），接下來的的n行包括n個k位的數字，允許調整後的數字有前導0（例如000123代表123）。

輸出

每組資料輸出一個整數，為調整後最大數字與最小數字之間的最小內插補點。

樣例輸入

樣例輸出

3
2700

提示

第二組樣例可以将原順序(1，2，3，4)調整為（3，1，4，2），則第二個數字變為5237，第三個數字變為2537，分别為這樣變換後的最大值和最小值，可以驗證這樣變換後的內插補點2700為最小內插補點。

題目連結：http://acm.hust.edu.cn/problem/show/1586

分析：直接k！的去枚舉全排列，将所有列都重新排列，然後暴力處理出來每一行的新數字，再維護一個最大值一個最小值相減即可。

數組a用來記錄輸入的字元串，數組b用來記位數，然後進行全排列，數組c用來裝數組a全排列後的值，注意數組c要清零

要用到next_permutation全排列，自動生成下個序列！詳細解釋請參考我的部落格！

下面附上AC代碼：

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 char a[10][10];
 4 int main()
 5 {
 6     int n,k;
 7     while(cin>>n>>k)
 8     {
 9         int b[10];
10         for(int i=1;i<=n;i++)
11             cin>>a[i];
12         for(int i=1;i<=k;i++)
13             b[i]=i;
14         int m=1;
15         for(int i=1;i<=k;i++)
16             m*=i;//直接求k！用m來裝k全排列的可能性
17         int output=0x3f3f3f3f;
18         for(int i=1;i<=m;i++)
19         {
20             next_permutation(b+1,b+1+k);//全排列
21             int c[10];
22             memset(c,0,sizeof(c));
23             for(int i=1;i<=n;i++)
24             {
25                 for(int j=1;j<=k;j++)
26                 {
27                     c[i]=c[i]*10+a[i][b[j]-1]-'0';//數組c用來裝數組a排列後的值
28                 }
29             }
30             sort(c+1,c+1+n);//排序，将數組c中的值進行升序排列
31             output=min(output,c[n]-c[1]);//維護一個最大值一個最小值相減，求最小內插補點
32         }
33         cout<<output<<endl;
34     }
35     return 0;
36 }

作　　者：Angel_Kitty

出　　處：https://www.cnblogs.com/ECJTUACM-873284962/

關于作者：阿裡雲ACE，目前主要研究方向是Web安全漏洞以及反序列化。如有問題或建議，請多多賜教！

特此聲明：所有評論和私信都會在第一時間回複。也歡迎園子的大大們指正錯誤，共同進步。或者直接私信我

聲援部落客：如果您覺得文章對您有幫助，可以點選文章右下角【推薦】一下。您的鼓勵是作者堅持原創和持續寫作的最大動力！

歡迎大家關注我的微信公衆号IT老實人(IThonest)，如果您覺得文章對您有很大的幫助，您可以考慮賞部落客一杯咖啡以資鼓勵，您的肯定将是我最大的動力。thx.

我的公衆号是IT老實人(IThonest)，一個有故事的公衆号，歡迎大家來這裡讨論，共同進步，不斷學習才能不斷進步。掃下面的二維碼或者收藏下面的二維碼關注吧(長按下面的二維碼圖檔、并選擇識别圖中的二維碼)，個人QQ和微信的二維碼也已給出，掃描下面👇的二維碼一起來讨論吧！！！

歡迎大家關注我的Github，一些文章的備份和平常做的一些項目會存放在這裡。

HUST 1586 數字排列

1586 - 數字排列