解题思路

要把这些数重新排列后拼接起来，让拼出的整数最大。关键问题只有一个：两个数 a 和 b，谁排在前面？

办法是分别试一下两种拼法：

• a 在前、b 在后，拼出 a+b；
• b 在前、a 在后，拼出 b+a。

哪个拼出来大，哪个就排在前面。比如 30 和 1：301 > 130，所以 30 排在 1 前面，结果是 301，和样例一致。

为什么不能用“直接比大小”呢？比如 9 和 90：9 比 90 小，但 990 > 909，所以 9 要排在 90 前面。用“比拼接结果”的方法，这种聪明的情况也自然正确。

做法：

1. 把每个数当作字符串读入（拼接和比较都很方便，也不会超出整数范围）；
2. 自定义排序规则：如果 a+b > b+a，那么 a 排在 b 前面；
3. 排好序后按顺序拼接，就是最大的结果。

特殊情况：如果所有数都是 0，拼出来是 000...，这时直接输出一个 0 就行。

参考代码

// P4556 结果最大：重新排列数字拼接，使结果最大
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 排序规则：a拼b比b拼a更大时，a排在前面
bool cmp(string a, string b) {
    return a + b > b + a;
}
int main() {
    int n;
    cin >> n;
    vector<string> v;
    for (int i = 0; i < n; i++) {
        string x;
        cin >> x;
        v.push_back(x);
    }
    sort(v.begin(), v.end(), cmp);   // 按拼接更大的顺序排序
    string ans;
    for (int i = 0; i < n; i++) ans += v[i];  // 依次拼接
    if (ans[0] == '0') cout << "0" << endl;   // 全为0时结果就是0
    else cout << ans << endl;
    return 0;
}

复杂度分析

• 排序 n 个数是 O(n log n)，每次比较都要拼接两个字符串，开销等于数字长度（很小）。
• 总时间复杂度 O(n log n × L)，L 是数字位数；空间复杂度 O(n × L)。