洛谷：P1012：拼数

题目

P1012：拼数

分析

这道题目是《深入浅出程序设计竞赛（基础篇）》第九章“排序”的收尾题，其中涉及的排序很有意思，所以列出。

先分析样本数据：¹

13 312 343 => 343|312|13
7 13 4 246 => 7|4|246|13

显然，这里的比较不是简单的“哪个字符串/数字更大”那么简单。

我们看一个实例：

321 32 407 135 13 217

如果按照单纯的字符串大小来排序，最后串联起来的字符串是：407|321|32|217|135|13。显然，因为321>32，程序会先连接321，再连接32，得到32132。但是，32|321会更大一点。所以这提示我们，这里的比较必须考虑到“待比较的两个字符串的两种拼接方式”产生的结果的“大小”。代码如下：

bool compare(const string &a, const string &b)
{
    return a + b > b + a;  // 比较a+b和b+a的大小
}

搞定这个排序算法后，代码就很直接的。

答案

思考

这里的“排序”是关键！