/*======================================================================
[NOIp 1998 提高组]Probelm 2 连接多位数
总时间限制: 10000ms 内存限制: 65536kB
描述
设有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
样例输出
3433213
[问题分析]
举例说明正常的字符串比较缺陷！
如：A=’321’，B=’32’，按照标准的字符串比较规则因为A>B，
所以A+B > B+A ，而实际上’32132’< ’32321’。
所以，自定义一种字符串的比较规则：
即如果A+B>B+A,则我们认为A>B。且可以证明：如果A+B>=B+A,B+C>=C+B,则一定有：A+C>=C+A。(注意，这个地方的加号是字符串连接)
这样一来，程序就很简单了。
分3步，先把n个数字转换成字符串存储；
再按照自定义的规则把n个字符串排序；
最后按照从大到小的顺序输出这些字符串。
小结：有些问题看起来是数学问题，认真分析会发现用字符串处理很简单。
另外，一定要掌握有关字符串的各种函数，以免用到时自己编子程序。
注：这个题是2011百度实习生笔试题，上面的分析在百度文库“2011百度实习生笔试题”复制而来。
http://wenku.baidu.com/link?url=HmZNHTkL7rm2vnC4XZKs6Ero0_78Bp5hMtvHMHdkaJrRn_GcyBZLivk2sydEL2oC7msYRQ5U6ZbY4a6M3PJhJ5zCEJEXNacXziF-uexIzpq
========================================================================*/
1 #include<stdio.h>
2 #include<string.h>
3 int intToStr(int x,char a[]);//把十进制x转成字符串,存储在字符串a。返回0表示出错。返回1表示成功
4 int cmp(int x,int y);//把x和y当字符串，自定义一种字符串的比较规则，即如果x+y>y+x,则我们认为x>y。
5 int main()
6 {
7 int n,i,a[25],j,k,t;
8 freopen("9.in","r",stdin);
9 scanf("%d",&n);
10 for(i=0;i<n;i++)
11 {
12 scanf("%d",&a[i]);
13 }
14 //下面按自定义的规则对那n个数排序。从大到小排序
15 for(i=0;i<n-1;i++)
16 {
17 k=i;
18 for(j=i+1;j<n;j++) //寻找a[i+1]~a[n-1]当中最小的元素并把它的下标记录到k里面。
19 if(cmp(a[j],a[k])>0) //if(a[j]>a[k])
20 k=j;
21 if(i!=k)
22 {
23 t=a[k];
24 a[k]=a[i];
25 a[i]=t;
26 }
27 }
28 //下面输出按自定义规则排序后的数字
29 for(i=0;i<n;i++)
30 {
31 printf("%d",a[i]);
32 }
33 printf("\n");
34 return 0;
35 }
36 int cmp(int x,int y)//把x和y当字符串，自定义一种字符串的比较规则，即如果x+y>y+x,则我们认为x>y。
37 {
38 char a[30],b[30];
39 char ab[60],ba[60];
40 intToStr(x,a);
41 intToStr(y,b);
42 strcpy(ab,a);
43 strcat(ab,b);
44 strcpy(ba,b);
45 strcat(ba,a);
46 return strcmp(ab,ba);
47 }
48 int intToStr(int x,char a[])//把十进制非负整数x转成字符串,存储在字符串a。
49 {//返回0表示出错。返回1表示成功
50 int i,len;
51 char t;
52 if(x<0) return 0;
53 if(x==0)
54 {
55 a[0]='0';
56 a[1]='\0';
57 return 1;
58 }
59 else
60 {
61 i=0;
62 while(x>0)
63 {
64 a[i]=x%10+'0';
65 x=x/10;
66 i++;
67 }
68 a[i]='\0';
69 len=i;
70 for(i=0;i<len/2;i++)
71 {
72 t=a[i];
73 a[i]=a[len-1-i];
74 a[len-1-i]=t;
75 }
76 return 1;
77 }
78 }
//上面这个整数转字符串的函数其实函数库有相应的库函数。
/*
itoa 注意：这个不是C的标准函数，不是所有的编译器都支持的。
功 能:把一整数转换为字符串
用 法:char *itoa(int value, char *string, int radix);
详细解释:itoa是英文integer to array(将int整型数转化为一个字符串,并将值保存在数组string中)的缩写.
参数：
value: 待转化的整数。
radix: 是基数的意思,即先将value转化为radix进制的数，范围介于2-36，比如10表示10进制，16表示16进制。
* string: 保存转换后得到的字符串。
返回值：
char * : 指向生成的字符串， 同*string。
备注:该函数的头文件是"stdlib.h"
*/
/*
C语言库函数名: atoi
原型: int atoi(const char *nptr);
功 能: 把字符串转换成整型数.
名字来源:array to integer 的缩写.
函数说明: atoi()会扫描参数nptr字符串，如果第一个字符不是数字也不是正负号返回零，
否则开始做类型转换，之后检测到非数字或结束符 \0 时停止转换，返回整型数。
*/
