题解：P1012 [NOIP 1998 提高组] 拼数

由 $a \succ b$ 得 $V(a) \cdot 10^{l_b} + V(b) > V(b) \cdot 10^{l_a} + V(a)$.

移项：$V(a)(10^{l_b} - 1) > V(b)(10^{l_a} - 1)$

变形为：$\frac{V(a)}{10^{l_a}-1} > \frac{V(b)}{10^{l_b}-1}$ —— (1)

同理，由 $b \succ c$ 可得 $\frac{V(b)}{10^{l_b}-1} > \frac{V(c)}{10^{l_c}-1}$ —— (2)

由 (1) 和 (2) 推出： $\frac{V(a)}{10^{l_a}-1} > \frac{V(c)}{10^{l_c}-1}$

将其还原：

即 $a+c > c+a$，也就是 $a \succ c$，QED。

假设存在一个最大整数的序列 $T = a_1a_2\dots a_n$，它不是按照我们定义的规则排序的。

既然它没按规则排，那么在 $T$ 中一定至少存在一对相邻的数字 $a_i$ 和 $a_{i+1}$，使得 $a_{i+1} \succ a_i$，即 $a_{i+1} + a_i > a_{i} + a_{i+1}$。

现在，我们交换 $a_i$ 和 $a_{i+1}$ 的位置，得到新序列 $T'$。

由于 $a_{i+1}a_i > a_ia_{i+1}$，且这两个字符串前面和后面是完全一样的，因此 $T' > T$。

这与假设矛盾，QED。

第一想法是按字典序排序嘛，数字比大小先比高位。

发现一个问题是，321 和 32 最后得出的数字是 32321，后者字典序小，反而在前面。

那改一下策略呢？先逐位比较，再判断长短。

但这种“打补丁”式的逻辑非常烧脑：如果多出的部分又是另一个数的前缀怎么办？递归下去逻辑会变得极其臃肿且容易出错。

回到问题的本质，比较最终数字的大小。

先考虑特殊的情况，两个字符串 $a,b$，拼成 $ab$ 和 $ba$。

这里的关键直觉是如果 $ab > ba$，那么在最终的答案里，$a$ 就应该排在 $b$ 的前面。

看看是否能推广到多个数。

尝试证明结论，就有了。