题解：P1012 [NOIP 1998 提高组] 拼数
__Aha__
·
·
题解
有错误请指出。
不太会用 Markdown，非常抱歉。
设数字字符串 x 的长度为 l_x，其数值为 V(x)。
首先定义字符串的连接 a+b 为：
f(a, b) = V(a) \cdot 10^{l_b} + V(b)
又定义的比较规则 \succ 为：
a \succ b \iff a+b > b+a
即：
V(a) \cdot 10^{l_b} + V(b) > V(b) \cdot 10^{l_a} + V(a)
首先有这个：若 a \succ b 且 b \succ c，则 a \succ c。
:::info[证明]
由 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}
将其还原：
V(a)(10^{l_c} - 1) > V(c)(10^{l_a} - 1)
V(a) \cdot 10^{l_c} + V(c) > V(c) \cdot 10^{l_a} + V(a)
即 a+c > c+a，也就是 a \succ c，QED。
::::
然后又有：按照上述规则排序得到的序列 S = s_1s_2\dots s_n 一定是最大的。
::::info[证明，反证]
假设存在一个最大整数的序列 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。
::::
就做完了。
::::info[怎么想到的]
第一想法是按字典序排序嘛，数字比大小先比高位。
发现一个问题是，321 和 32 最后得出的数字是 32321，后者字典序小，反而在前面。
那改一下策略呢？先逐位比较，再判断长短。
但这种“打补丁”式的逻辑非常烧脑：如果多出的部分又是另一个数的前缀怎么办？递归下去逻辑会变得极其臃肿且容易出错。
回到问题的本质，比较最终数字的大小。
先考虑特殊的情况，两个字符串 a,b，拼成 ab 和 ba。
这里的关键直觉是如果 ab > ba，那么在最终的答案里，a 就应该排在 b 的前面。
看看是否能推广到多个数。
尝试证明结论，就有了。
::::