**原题链接**

题目描述

设有n个正整数(n ≤ 20),将它们联接成一排,组成一个最大的多位整数。

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

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

输入描述:

第一行,一个正整数n。
第二行,n个正整数。

输出描述:

一个正整数,表示最大的整数

分析:

要用一组正整数组成一个最大的多位整数,很自然的想到给这组正整数

按字典序排序,然后按字典序从大到小把这组正整数连接起来。

但,我们来看这么一组数据:30300

它们可以组成:

3030030030

两个数字。

显然:

\[\begin{cases}
30300>30030 \\
X(300)>X(30)
\end{cases}
\]

其中X(n)为表示字典序大小的函数。

这和我们直觉上的大字典序在前,后链接小字典序所组合多位整数更大的判断不同。

所以,我们不能直接比较两个数字典序就的大小,而是要比较两个数前后放置组成的数是否比较大。

即:

\[F(x)=max\left\{A+B,B+A\right\}
\]

其中,F(x)为两正整数组合后的数值大小,AB为正整数。

代码

#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;
}
05-07 15:11