P1012 拼数

admin

https://www.luogu.org/problemnew/show/P1012

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

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

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

输入格式：
第一行，一个正整数n。
第二行，n个正整数。

输出格式：
一个正整数，表示最大的整数

universehyf

字符串比较

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. string s[21];
   
5. int n,i;
   
6. bool mycomp(string x,string y)
   
7. {return x+y > y+x;}
   
8. int main()
   
9. {
   
10.     cin>>n;
    
11.     for(i=0; i<n; i++) cin>>s[i];
    
12.     sort(s,s+n,mycomp);
    
13.     for(i=0; i<n; i++) cout<<s[i];
    
14.     return 0;
    
15. }

复制代码

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int n;
    
14. string a[21];
    
15. bool cmp(string x,string y)
    
16. {
    
17.         return x+y>y+x;
    
18. }
    
19. int main()
    
20. {
    
21.         scanf("%d",&n);
    
22.         for(int i=1;i<=n;i++)
    
23.                 cin>>a[i];
    
24.         sort(a+1,a+1+n,cmp);
    
25.         for(int i=1;i<=n;i++)
    
26.                 cout<<a[i];
    
27.         return 0;
    
28. }

复制代码

王令欧

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.         int n,t,gud=0,i,j;
   
6.         int num[21],reco[21],geno[21],c[21]={0};
   
7.         long long int ans=0;
   
8.         scanf("%d",&n);
   
9.         for(i=0;i<=n-1;i++)
   
10.         {
    
11.                 scanf("%d",&num[i]);
    
12.         }
    
13.         for(i=0;i<=n-1;i++)
    
14.         {
    
15.                 reco[i]=num[i];
    
16.                 geno[i]=num[i];
    
17.                 while(reco[i]/10!=0)
    
18.                 {
    
19.                         reco[i]=reco[i]/10;
    
20.                         c[i]++;
    
21.                 }
    
22.                 c[i]++;
    
23.                 if(gud<c[i])
    
24.                         gud=c[i];
    
25.         }
    
26.         for(i=0;i<=n-1;i++)
    
27.                 for(j=c[i];j<=gud-1;j++)
    
28.                         geno[i]=geno[i]*10;
    
29.         for(i=0;i<=n-1;i++)
    
30.                 for(j=i+1;j<=n-1;j++)
    
31.                         if(geno[i]>geno[j])
    
32.                         {
    
33.                                 t=geno[i];
    
34.                                 geno[i]=geno[j];
    
35.                                 geno[j]=t;
    
36.                                
    
37.                                 t=num[i];
    
38.                                 num[i]=num[j];
    
39.                                 num[j]=t;
    
40.                         }
    
41.         t=1;
    
42.         for(i=0;i<=n-1;i++)
    
43.         {
    
44.                 if(i!=0)
    
45.                         for(j=0;j<=c[i-1]-1;j++)
    
46.                                 t=t*10;
    
47.                 ans=ans+num[i]*t;
    
48.         }
    
49.         printf("%d",ans);
    
50.         return 0;
    
51. }

复制代码

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. string s[25];
   
4. int i,j,n;
   
5. bool b(int a,int b)///判断哪个在前，哪个在后
   
6. {
   
7.     int la=s[a].size(),lb=s[b].size();
   
8.     string s1=s[a]+s[b],s2=s[b]+s[a];
   
9.     for (int k=0; k<=la+lb-1; k++)
   
10.     {
    
11.         int x1=s1[k]-'0',x2=s2[k]-'0';
    
12.         if (x1==x2) continue;
    
13.         else if (x1<x2) return 0;
    
14.         else return 1;
    
15.     }
    
16.     return 1;
    
17. }
    
18. int main()
    
19. {
    
20.     cin>>n;
    
21.     for (i=1; i<=n; i++) cin>>s[i];
    
22.     for (i=1; i<=n; i++)
    
23.         for (j=1; j<=n; j++)
    
24.         {
    
25.             if (b(i,j)) swap(s[i],s[j]);
    
26.         }
    
27.     for (i=1; i<=n; i++) cout<<s[i];
    
28.     return 0;
    
29. }
    

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int n;
   
5. string s[30];
   
6. bool cmp(string x,string y)
   
7. {
   
8.     string a=x+y,b=y+x;
   
9.     return a>b;
   
10. }
    
11. int main()
    
12. {
    
13.     cin>>n;
    
14.     for(int i=1;i<=n;i++)cin>>s[i];
    
15.     sort(s+1,s+n+1,cmp);
    
16.     for(int i=1;i<=n;i++)cout<<s[i];
    
17.     return 0;
    
18. }
    

复制代码

admin

找到排序的方法，将大数字放在前面小数字放在后面接起来就行了，关键就是如何判断大小！
传统上的整数比较是位数多的大，这里显然不对比如 9 应该放在55 的前面
或者按字典序那样比较，但是也不对，比如98 应该放在9 的后面 34却要放在3的前面
找到这个比较的方法写好这个函数就是此题的关键 ！！！

1. #include<iostream>
   
2. using namespace std;
   
3. const int mn=25;
   
4. int n,i,j;
   
5. string s[mn];
   
6. bool isbig(string s1,string s2)
   
7. {
   
8. 
   
9.     if (s1==s2) return 1; ///相等特判
   
10.     else
    
11.     {
    
12.         int i=0, b=0;
    
13.         int l1=s1.size();
    
14.         int l2=s2.size();
    
15.         while (b==0)  ///首尾相连循环比较!!!
    
16.         {
    
17.             if (s1[i%l1]>s2[i%l2])  b=1;
    
18.             else if (s1[i%l1]<s2[i%l2]) b=-1;
    
19.             else i++;
    
20.         }
    
21.         return (b>=0);
    
22.     }
    
23. }
    
24. int main()
    
25. {
    
26.     cin>>n;
    
27.     for (i=0; i<=n-1; i++)  cin>>s[i];
    
28.     ///排序，不讲究了
    
29.     for (i=0; i<=n-2; i++)
    
30.         for (j=i+1; j<=n-1; j++)
    
31.             if (!isbig(s[i],s[j]))  swap(s[i],s[j]);
    
32. 
    
33.     for (i=0; i<=n-1; i++)  cout<<s[i];
    
34.     return 0;
    
35. }
    

复制代码