【题目描述】

      设有n个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。

       例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213； 

       又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613

【输入】

       两行，第一行n。表示有n个数。

       第二行是 n个数。

【输出】

连接成的多位数

【输入样例】

3  13 312 343

【输出样例】

34331213

【题目分析】

 1.字符串排序的规则：首先按字典序，然后看串长度。如7>414 321>32

 2.

【贪心思路】

使用贪心思想，首先把每两个数进行一次组合，把组合过后较大的那个结果的前面那个数排在前面，后面的那个数排在后面；以此类推之后，最后就能得出n个数组合的最大值。

【解题思路】

第一种方法是使用结构体来存放输入数字的大小和长度，类型都是整形，但是两个整形的数组合起来比较麻烦，比如说两个整数a和b，长度分别为lena和lenb，组合数为a*10^lenb+b和b*10^lena+a,比较这两个数的大小，比较麻烦；

例如13 和312 两个组合成   不同数字，可以是

13312和31213

组合过程可以用13*10^3+312  和 312*10^2+13

 第二种方法我使用字符串来存放输入的数字，字符串组合就比较简单了，同样两个数字a和b,不用考虑两个字符串的长度，字符串组合直接使用加符号，所以组合数为a+b和b+a，比较大小也可以直接比较(return a+b>b+a?a+b:b+a)，是不是比整形方法的简单。

【参考代码1】

#include<iostream>  #include<cmath>  #include<algorithm>  using namespace std;  struct num {  	long long x,y;//x表示这个数字，y表示这个数字的长度  } v[25];  int comp(num a,num b) {  	return a.x*pow(10,b.y)+b.x>b.x*pow(10,a.y)+a.x;//每两个数进行组合，找出最大的数字排列顺序  }  int main() {  	int n,temp,len=0; //n个数，临时变量， 长度   	cin>>n;  //n个数   	for(int i=1; i<=n; i++) {  		cin>>v[i].x; //读入这个数   		temp=v[i].x; //把这个数赋值给临时变量   		len=0; //长度初始化   		while(temp) { //计算这个数字的长度  			len++;  			temp/=10;  		}  		v[i].y=temp; //把长度赋值给结构体   	}  	sort(v+1,v+1+n,comp);  //结构体排序   	for(int i=1; i<=n; i++)   		cout<<v[i].x;   //输出   	return 0;  }

【参考代码2】

#include<iostream>  #include<algorithm>  using namespace std;  int cmp(string a,string b)//定义字符串排序  {      if(a+b>b+a)return 1;           else return 0;  }  int main()  {    int n;    string a[25];    cin>>n;    for(int i=1;i<=n;i++)        cin>>a[i];    sort(a+1,a+1+n,cmp);    for(int i=1;i<=n;i++)        cout<<a[i];    return 0;  }

【问题】：

为什么 cmp函数里不直接写 return a>b?

例如下面的例子：

1 10

这两个数如果用字典序排列，那么10>1 。这样组合出来的数据是101。很明显这样组合不是最大的，最大的组合应该是110。所以，直接按照字典序排序是不对的，我们需要将数据进行两两组合，最后看结果。

101 和110的字典序相比，明显110的字典序更大。

(adsbygoogle = window.adsbygoogle || []).push({});