题解 | #拼数#

题目大意

给你n个正整数，把它们拼成一个最大的整数。

思路分析

贪心。不是按数字大小排，是按a+b > b+a的方式排。因为数字长度不同，直接比大小不对，比如32和3，3应该排在32前面，因为3+32=332 > 323。

复杂度分析

O(n log n)，排序的复杂度。

参考代码

#include <bits/stdc++.h>
using namespace std;
bool cmp(string a,string b) {
    return a+b>b+a;
}
int main(){
    int n;
    cin>>n;
    vector<string> nums(n);
    for (int i=0;i<n;i++) cin>>nums[i];
    sort(nums.begin(), nums.end(),cmp);
    for (string s:nums) cout<<s;
    return 0;
}