问题 G: 最大整数

题目描述

设有n个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。 例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213 又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613

输入

输入格式如下： 第一行为正整数n，第2行为n个正整数，2个正整数之间用空格间隔。

输出

输出n个数连接起来的最大整数

样例输入

3
13 312 343

样例输出

34331213

问题分析

将一系列字符串排序拼接，使得最终形成的单一字符串在字典序上尽可能大。这不是传统意义上的字典序排序，因为它考虑的是两个字符串拼接后的字典序，而不是单个字符串本身的字典序。

#include <bits/stdc++.h>
using namespace std;

bool cmp(const string& a,const string& b) {
    return a+b>b+a; //如果a+b大于b+a，a应该排在b的前面
}

int main() {
    int n;
    cin>>n;
    vector<string> a(n); //名字叫a的这个容器里面存了n个string类型的元素
    for(int i=0;i<n;i++) {
        cin>>a[i];
    }
    sort(a.begin(),a.end(),cmp); //对其中的元素按cmp规则排序
    for(const string&t : a) { //t是用于取a中的元素
        cout<<t; //也就是每次取出a中一个元素拼接在一起
    }
}