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

喵仔牛奶 · 2025-08-08 20:38:37 · 题解

Solution

用通俗的语言解释一下这个题是怎么回事。

将题目中的数看作字符串，A+B 表示 A,B 两个字符串的拼接，A<B 表示 A 的字典序比 B 小。

我们定义 \boldsymbol A 比 \boldsymbol B 优，当且仅当 A+B>B+A。

我们想要说明，如果 A 比 B 优，B 比 C 优，则 A 比 C 优：

• 设 a,b,c 分别为 A,B,C 这三个字符串表示的数，\lvert A\rvert 表示 A 的长度。
• 那么我们知道 \frac{a}{10^{\lvert A\rvert}-1}>\frac{b}{10^{\lvert B\rvert}-1}，\frac{b}{10^{\lvert B\rvert}-1}>\frac{c}{10^{\lvert C\rvert}-1}，那么当然有 \frac{a}{10^{\lvert A\rvert}-1}>\frac{c}{10^{\lvert C\rvert}-1}，也就是说 A 比 C 优了。

那么这个比较就具有了传递性！

我们发现，对于相邻的 A,B，如果 A 比 B 优，那么交换 A,B 后答案更加大。

对于一种连接方式，一直交换这样的相邻串，最后得到的串就是从优到劣排序后的连接方式（根据传递性）。那么所有连接方式的答案都不会比排序后的答案更大，因此最优解就是从优到劣排序啦！

直接定义自定义比较函数 cmp，然后使用 sort 排序即可。

Code

#include <bits/stdc++.h>
using namespace std;
string s[50];
int n;
bool cmp(string A, string B) {
    return A + B > B + A;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> s[i];
    sort(s + 1, s + 1 + n, cmp);
    for (int i = 1; i <= n; i ++)
        cout << s[i];
    return 0;
}