字符串连接问题

设有n个正整数，将他们连接成一排，组成一个最大的多位整数。例如:n=3时，3个整数13,312,343,连成的最大整数为:34331213

又如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613

输入：N

N个数

输出:连接成的多位数

实际上，可以将问题扩展成字符串拼接，求最大字串的问题。

由于题目中不能直接按字典序来排序贪心，所以要选择正确的贪心策略成为问题关键。

比较规则定义：对于任意字符串a，b，如果存在 ab（ab表示a和b连结操作，’<’ 表示字典序大小的比较），那么我们就定义 a 是先序于 b 的。

下面要证明的是，对n个字符串，用上面的规则是可排序的。

证明：

首先，他是可比较的，这个没有疑问。

那么问题就在于，他是不是会出现一个环。如果出现了一个环，那就没办法排序了；如果没有出现环，我们就可以对他进行拓扑排序。

假设，这个比较规则是具有传递性的，也就是说如果 ab那么，一定存在ac。即 a先序于b，b先序于c，则一定有a先序于c。如果传递性成立，那么就不可能出现环，那么也就证明了这个比较规则是可排序的。

下面来证明传递性。

重新描述如下：对于任意字符串a，b，c，如果ab且bc。那么一定有ac。

首先，一个字符串可以表达为一个z进制的数。z可以是字母表的大小，比如26，52，62或者128，256。

然后我们定义|a|，|b|，|c|，为字符串a，b，c的长度。

那么，ab = a * z ^ |b| + b , ba = b * z ^ |a| + a

bc = b * z ^ |c| + c , cb = c * z ^ |b| + b

ac = a * z ^ |c| + c , ca = c * z ^ |a| + a

因为字符串ab和ba的长度是一样的，所以ab的字典序小于ba等价于代数上ab。同理还有bc和ac。

下面就来证明下面的代数推导，ab ac。

由上面的式子得到：

a * z ^ |b| + b < b * z ^ |a| + a …………………..A

b * z ^ |c| + c < c * z ^ |b| + b …………………..B

化简A: a *(z^|b|-1) < b *(z^|a|-1)

因为 |a|>0, 所以 z^|a|-1 > 0

所以 a * (z ^ |b| - 1) / (z ^ |a| - 1)

同理化简B：b * (z ^ |c| - 1) < c * (z ^ |b| - 1)

B < c * (z ^ |b| - 1) / (z ^ |c| - 1)……………….D

由C，D得： a * (z ^ |b| - 1) / (z ^ |a| - 1) < c * (z ^ |b| - 1) / (z ^ |c| - 1)

于是有： a * (z ^ |c| - 1) < c * (z ^ |a| - 1)

a * z ^ |c| + c < c * z ^ |a| + a

这就得到了ac。

于是，证明了这个规则的传递性，也就证明了不存在环，即可排序性 。

证毕

有了比较原则和证明，实际解题可以使用任意排序方法，最后依次拼接即可