思路与证明

• 核心策略：将所有数转成字符串，按自定义比较器排序：对任意两个字符串 $x$、$y$，若 $x+y > y+x$ 则令 $x$ 在前，否则 $y$ 在前。排序后顺序拼接即为最优解。
• 正确性（交换论证）：若相邻的两个字符串按上述比较器的顺序放置能得到更大的两段拼接（即 $x+y \ge y+x$），则任何最优结果中它们都不应反着放；否则交换可使结果不小。对所有相邻对都满足该性质的全局序即为最优。
• 边界处理：若排序后首元素为字符串 "0"，说明所有数均为 $0$，直接返回 "0"。
• 复杂度：设每个数的字符串长度上界为 $L$（此处 $L \le 10$）。排序比较一次为 $O(L)$，总复杂度为 $O(n \log n \cdot L)$，空间复杂度 $O(n \cdot L)$。

C++

题目内容

在一个奇特的王国里，国王计划举办一次盛大的庆典。庆典上会举行一场皇家号码展示--由n张金色牌子组成，每张牌子上刻着一个正整数(这些数可能相同，也可能不同)。 展示的规则很奇怪:

• 侍卫会将所有牌子排成一行，从左到右依次摆放。
• 每张牌子上刻的数字会直接写在展示牌上，不会加任何空格或标点，也不能把一张牌拆开。
• 所有牌子摆好后，从左到右拼成的整个数字，就是庆典的“皇家号码”。

国王有一个要求:这个皇家号码必须尽可能大，以象征王国的繁荣与强大。

你是皇家顾问，需要告诉侍卫一种排列顺序，让最终得到的皇家号码最大。

输入描述

第一行输入一个正整数$n(1≤n≤10^5)$。

第二行输入$n$个正整数$a_1,a_2,...,a_n (1≤a_i≤10^9)$。

输出描述

输出能够得到的最大皇家号码(用字符串形式表示)。

样例1

输入

3
13 312 343

输出

34331213