[NOIP 1998 提高组] 拼数

题意

给出 n 个正整数，可以任意调整顺序并首尾拼接，要求组成最大的整数。

思路

先看一个小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59// brute.cpp：小数据暴力解，使用选择序列递归枚举所有拼接顺序。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;

int n;
string a[MAXN];
bool used[MAXN];
int choose_order[MAXN]; // choose_order[i] 表示第 i 个位置放哪个原数
string best_answer;

string calc_answer() {
    string res = "";
    for (int i = 1; i <= n; i++) {
        res += a[choose_order[i]];
    }
    return res;
}

void update_answer() {
    string current = calc_answer();
    if ((int)current.size() > (int)best_answer.size() ||
        ((int)current.size() == (int)best_answer.size() && current > best_answer)) {
        best_answer = current;
    }
}

void dfs_order(int dep) {
    if (dep == n + 1) {
        update_answer();
        return;
    }

    // 这一层只记录第 dep 个拼接位置选择哪个数。
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            choose_order[dep] = i;
            dfs_order(dep + 1);
            used[i] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    best_answer = "";
    dfs_order(1);
    cout << best_answer << '\n';
    return 0;
}

暴力枚举所有排列，再拼接比较，复杂度是 n!。

正解只需要解决两个字符串 x 和 y 的相对顺序：

如果 x 在前，局部结果是 x+y；
如果 y 在前，局部结果是 y+x。

为了让整体最大，若 x+y > y+x，就应该让 x 排在 y 前面。按照这个比较规则排序后，把所有字符串连接起来就是答案。

例如 13 和 312：

text

1
213 + 312 = 13312
312 + 13 = 31213

所以 312 应该排在 13 前面。

Python 知识

输入数字不要转成整数排序，而要保留为字符串。
Python 排序默认使用 key，遇到这种“两两比较”规则时，可以用 functools.cmp_to_key。
比较函数返回负数表示第一个参数排在前面。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22from functools import cmp_to_key
import sys


def compare(x, y):
    if x + y > y + x:
        return -1
    if x + y < y + x:
        return 1
    return 0


def main():
    tokens = sys.stdin.read().split()
    n = int(tokens[0])
    numbers = tokens[1:1 + n]
    numbers.sort(key=cmp_to_key(compare))
    print("".join(numbers))


if __name__ == "__main__":
    main()

复杂度

排序比较次数为 $O(n \log n)$ 。设数字字符串长度上界为 L，每次比较会拼接并比较两个长度约 2L 的字符串，总复杂度约为 $O(n \log n \cdot L)$ 。

空间复杂度是 $O(nL)$ 。

总结

拼数不能按数值大小排序。真正的局部标准是比较 x+y 和 y+x，谁能让拼接结果更大，谁就排在前面。

[NOIP 1998 提高组] 拼数

目录

题意

思路

Python 知识

代码

复杂度

总结