P4671 连接数字（提高）

解题思路

第一步，打破"按大小排序"的思维定式。 这道题不能按数字大小直接排序！比如 7 和 13，7 虽然比 13 小，但连接时 7 要排在 13 前面，因为 713 比 137 大。正确的规则是：比较任意两个数 x 和 y，要看"x 接 y"和"y 接 x"哪个拼出来的数更大，谁大就让谁排前面。

第二步，把数当成字符串。 数字的位数可能不一样，直接用整数比大小不方便。我们把每个数当作字符串存进结构体 Num 的 str 字段里，比较的时候把两个字符串拼起来再比较。

第三步，写自定义比较函数。 cmp(x, y) 里先把 x.str 和 y.str 拼成 xFirst，把 y.str 和 x.str 拼成 yFirst，用 strcmp 比较两个拼接结果：如果 xFirst 更大，就让 x 排前面。sort 用这个规则排完，数组的顺序就是能连出最大数的顺序。

第四步，拼接输出。 按排好的顺序，把每个数的字符串依次输出，连在一起就是最大的多位整数，末尾换行。

想一想生活里的例子。 两个人比姓名接龙，要把两种顺序都拼出来比比看，哪个拼出来更大就选哪种。

边界情况： 每个数可能很长，字符串数组要开大一些（50）；比较时拼接的临时字符串也要够大（110），避免溢出。这个规则是一种"贪心"思想：每次比较都选局部最优的拼接顺序，最后整体拼出来就是最大的。

参考代码

// P4671 连接数字：把n个正整数连成一排，组成最大的多位整数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

struct Num {
    char str[50]; // 存一个正整数（当作字符串）
};

bool cmp(const Num &x, const Num &y) {
    // 比较 x放前面 还是 y放前面 连出来更大
    char xFirst[110], yFirst[110];
    strcpy(xFirst, x.str);
    strcat(xFirst, y.str);
    strcpy(yFirst, y.str);
    strcat(yFirst, x.str);
    return strcmp(xFirst, yFirst) > 0; // x在前更大，则x排前面
}

Num nums[1005];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> nums[i].str;
    }
    sort(nums, nums + n, cmp); // 排序
    for (int i = 0; i < n; i++) {
        cout << nums[i].str; // 依次连接输出
    }
    cout << endl;
    return 0;
}

复杂度分析

排序 n 个数需要 O(n log n) 次比较，每次比较要拼接两个字符串并比较，假设每个数最长 L 位，单次比较是 O(L)。总时间复杂度 O(n log n × L)。本题 n 和 L 都不大，速度很快。空间上要开一个 O(n) 的字符串数组。