【题目描述】

      设有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的字典序更大。