[NOIP 1998 提高组] 拼数

知识点

贪心、排序、字符串

解题思路

把每个正整数读成字符串。排序时，若a+b大于b+a，则把a放在b前面；最后依次拼接。

正确性说明

任意相邻a、b，其他前后缀固定时，交换二者只会改变中间的ab与ba，按较大的顺序放置不会变差。此比较可等价于无限重复字符串的字典序（或比较a/(10^|a|-1)与b/(10^|b|-1)），满足一致的弱序。不断消除逆序得到排序结果，因此全局最优。

易错点

如12和121、9和90不能按整数大小排；a+b=b+a时比较器必须返回false；不把结果转成整数。

复杂度

时间O(n log n·L)，空间O(nL)，L为单个数字字符串长度。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;vector<string>a(n);for(auto&s:a)cin>>s;sort(a.begin(),a.end(),[](const string&a,const string&b){return a+b>b+a;});for(auto&s:a)cout<<s;cout<<'\n';}