洛谷 P1012 拼数

链接

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个正整数。

输出格式：

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

输入输出样例

输入样例#1：

　　3
　　13 312 343

输出样例#1：

34331213

思路

这题如果是第一次做会有点难度，但是我以前做过同类的，借助字典序来算就会简单很多，对于字典序来说1234<3412，那么12和34这两个数就可以通过字典序来比较，这里设置一个比较函数compare，比较a+b和b+a的字典序，这边设置的是34在12的前面，所以要先输出（3412>1234）.之后借助sort函数排序，按照顺序输出即可。

代码

#include<iostream>
#include<algorithm> 

using namespace std;

bool compare(string a,string b)
{
    return a+b>b+a;
}

int main()
{
    int n;
    cin>>n;
    string num[n];
    for(int i=0;i<n;i++)
        cin>>num[i];
    sort(num,num+n,compare);
    for(int i=0;i<n;i++)
        cout<<num[i];
    return 0;
}