【例71.3】 拼最大整数

解题思路

比较两个数字字符串a,b时，若a+b>b+a就让a排前。按此比较器排序后直接拼接输出，不转回有限位整数。

正确性说明

若相邻两块a,b满足ab<ba，则交换使整个拼接串更大，其他前后缀不变。最优顺序不能存在这种逆序，按拼接比较排序消除全部可改善相邻对即可最大。

易错点

不能单纯按数值或字典序降序，例如9应排在91前。

复杂度

最长L位，时间O(nL log n)，空间O(nL)。

参考代码（C++11）

#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 &x, const string &y) { return x + y > y + x; });
    for (auto &s : a)
        cout << s;
    cout << "\n";
    return 0;
}