题解

给定$n$个字符串，求一种拼接顺序，使得得到的大字符串是所有可能性中字典序最小的。

有一种思路为：先把$n$个字符串按照字典顺序排序，然后将串起来的结果返回。这么做是错误的，比如：$B,BA$按照字典排序结果是$B,BA$，串起来的大写字符串为$”BBA”$，但是字典顺序最小的大写字符串是$”BAB”$，所以按照单个字符串的字典顺序进行排序的想法是行不通的。如果要排序，应该按照下文描述的标准进行排序。

假设有两个字符串，分别记为$a$和$b$，$a$和$b$拼起来的字符串表示为$a.b$。那么如果 $a.b$ 的字典顺序小于 $b.a$，就把字符串 $a$ 放在前面，否则把字符串 $b$ 放在前面。

每两个字符串之间都按照这个标准进行比较，以此标准排序后，再依次串起来的字符串就是结果。这样做为什么对呢？当然需要证明。

证明的关键步骤是证明这种比较方式具有传递性。

假设有 $、、a、 b、 c$ 三个字符串，它们有如下关系：

$a.b < b.a$

$b.c < c.b$

如果能够根据上面两式证明出 $a.c < c.a$， 说明这种比较方式具有传递性， 证明过程如下：

字符串的本质是 $K$ 进制数，比如， 只由字符$’a’~’z’$组成的字符串其实可以看作 $26$ 进制数。那么字符串 $a.b$ 这个数可以看作 $a$ 是它的高位， $b$ 是低位，即 $的长度次方a.b=a*K的b长度次方+b$。为了让证明过程便于阅读，我们把$的长度次方K 的 b 长度次方$记为$k(b)$。则原来的不等
式可化简为：

$a.b < b.a => ak(b) + b < bk(a) + a$ 不等式 1

$b.c < c.b => bk(c) + c < ck(b) + b$ 不等式 2

现在要证明 $a.c < c.a$，即证明 $ak(c)+c$ < $ck(a)+a$。

不等式 1 的左右两边同时减去 $b$， 再乘以 $c$，变为 $ak(b)c < bk(a)c+ac-bc$。不等式 2 的左右两边同时减去 $b$， 再乘以 $a$，变为 $bk(c)a + ca - ba < c*k(b)*a$。所以有如下不等式：

$bk(c)a + ca-ba < ck(b)a == ak(b)c < bk(a)c + ac - bc$

$=> bk(c)a + ca - ba < bk(a)c + ac-bc$

$=> bk(c)a - ba < bk(a)c - bc$

$=> ak(c) - a < ck(a) - c$

$=> ak(c) + c < ck(a) + a$

即 $a.c < c.a$，传递性证明完毕。

证明传递性后，还需要证明通过这种比较方式排序后，如果交换任意两个字符串的位置所得到的总字符串，将拥有更大的字典顺序。此处证明较简单，故省略。

总结：

1. 多利用进制的思想处理字符串问题。
2. 如$a.b<b.a$，则同样可得$a^\infty<b^\infty$，证明较为简单。