[NOIp 1998 提高组]Probelm 2 连接多位数【2011百度实习生笔试题】

/*======================================================================
[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 时停止转换，返回整型数。
*/