题目原型为洛谷 P1012 [NOIP1998 提高组] 拼数。本题的考点是自定义比较规则（贪心 + 排序）：拼出的数最大，比较的不是数字本身，而是两种拼接方式谁更大。

目标

完成本题后，你应该能够：

• 识别「不能按数字本身大小排序」的陷阱（反例 9 和 90）；
• 用 a+b > b+a 的拼接比较器定义排序规则；
• 理解为什么这个规则构成一个可传递的全序，从而贪心成立。

前置知识

• 字符串拼接与字典序比较；
• std::sort 的自定义比较器。

题目

设有 n 个正整数，将它们连接成一排，组成一个最大的多位数。

输入格式

• 第一行一个整数 n；
• 第二行 n 个正整数。

输出格式

一行一个整数，表示能拼出的最大的多位数。

数据范围

项目	范围
数字个数 n	1 ≤ n ≤ 20
每个数	不超过 10⁹ 的正整数

样例

样例输入

3
13 312 343

样例输出

34331213

样例解释

343 与 312 相比，343312 > 312343，所以 343 排前；312 与 13 相比，31213 > 13312，所以 312 排前，最终拼接 34331213。

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用等价的 pnpm 入口：

pnpm lab:run -- labs/chapter-11/exercise/E-11-03-concat-max
pnpm lab:score -- labs/chapter-11/exercise/E-11-03-concat-max

标准输出参与判题，调试信息请写入标准错误。

完成清单

• 样例输出与题目一致
• 「前缀关系」（如 9 与 90、32 与 321）的陷阱用例通过
• 能说出为什么比较 a+b 与 b+a 而非 a 与 b

思考题

1. 为什么 9 和 90 按「9 > 90」排序会得到 909 而不是更大的 990？
2. 如何证明 a+b > b+a 定义的关系是可传递的（从而排序后拼接最优）？

题解

点击查看题解

思路

两个数的相对顺序，只取决于两种拼接方式 a+b 与 b+a 谁更大。因此比较器写 return a + b > b + a; 即可。排序后按序拼接就是答案。

这个比较关系对应比较循环小数 a/(10^len(a) − 1)，是可传递的全序，所以贪心正确。

复杂度分析

• 时间复杂度：O(n log n · L)，L 为数字字符串长度；
• 空间复杂度：O(n · L)。