题目描述
设有n个正整数(n ≤ 20),将它们联接成一排,组成一个最大的多位整数。
例如:n=3时,3个整数13,312,343联接成的最大整数为:34331213
又如:n=4时,4个整数7,13,4,246联接成的最大整数为:7424613
输入描述:
第一行,一个正整数n。
第二行,n个正整数。
输出描述:
一个正整数,表示最大的整数
分析:
要用一组正整数组成一个最大的多位整数,很自然的想到给这组正整数
按字典序排序,然后按字典序从大到小把这组正整数连接起来。
但,我们来看这么一组数据:30300。
它们可以组成:
30300、30030
两个数字。
显然:
\[\begin{cases}
30300>30030 \\
X(300)>X(30)
\end{cases}
\]
30300>30030 \\
X(300)>X(30)
\end{cases}
\]
其中X(n)为表示字典序大小的函数。
这和我们直觉上的大字典序在前,后链接小字典序所组合多位整数更大的判断不同。
所以,我们不能直接比较两个数字典序就的大小,而是要比较两个数前后放置组成的数是否比较大。
即:
\[F(x)=max\left\{A+B,B+A\right\}
\]
\]
其中,F(x)为两正整数组合后的数值大小,A、B为正整数。
代码
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string a[40];
bool cmp(const string &a,const string &b){
return a+b<b+a;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n,cmp);
string s;
for(int i=n-1;~i;i--)s+=a[i];
cout<<s<<endl;
return 0;
}