HUST 1586 数字排列
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 3
010
909
012
6 4
5237
2753
7523
5723
5327
2537样例输出
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 }本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-02-12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
