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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python专栏

浅尝Python快速排序

1324
来自专栏计算机视觉与深度学习基础

Leetcode 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 a...

2555
来自专栏编程之旅

唠唠快速排序算法

每一个从事计算机相关方向工作的同学一定听说过快速排序算法,在面试的准备过程中,快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。

1052
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-06.总结二维数组,面向对象

1:二维数组(理解) (1)元素是一维数组的数组。 (2)格式: A:数据类型[][] 数组名 = new 数据类型[m][n]; B:数据类型[][]...

2724
来自专栏计算机视觉与深度学习基础

Leetcode 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 a...

3554
来自专栏take time, save time

你所能用到的数据结构(五)

七、骚年,这就是你的终极速度了吗? 在介绍了前面的几个排序算法之后,这一次我准备写写快速排序,快速排序之所以叫快速排序是因为它很快,它是已知实践中最快的排序算...

2805
来自专栏HTML5学堂

原生JS | 当兔子遇到鸡

HTML5学堂-码匠:当兔子遇到鸡,会怎样呢?先别急,看个小视频~ 视频内容 当兔子遇到鸡 —— 不要害怕和别人不一样,在这个世界上,你就是独一无二的自己! 不...

46110
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(11-15打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

1161
来自专栏北京马哥教育

史上最简单!冒泡、选择排序的Python实现及算法优化详解

1、排序概念 内部排序和外部排序 根据排序过程中,待排序的数据是否全部被放在内存中,分为两大类: 内部排序:指的是待排序的数据存放在计算机内存中进行的排序过程;...

5074
来自专栏算法channel

不基于比较的基数排序原理图解

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

45013

扫码关注云+社区

领取腾讯云代金券