[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()

Guide 风格代码

cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-14 14:55
 * update_at: 2026-08-14 14:55
 */
#include <iostream>
#include <string>
#include <algorithm>

const int max_n = 25;  // n <= 20

// 比较规则：x 排在 y 前面能拼出更大的数时返回 true。
// 只看拼接后的 x+y 和 y+x，谁大谁在前
bool better(const std::string& x, const std::string& y) {
    return x + y > y + x;
}

int main() {
    int n;
    std::cin >> n;
    std::string a[max_n];  // 数字按字符串保存，避免拼接时溢出
    for (int i = 0; i < n; i += 1) {
        std::cin >> a[i];
    }

    std::sort(a, a + n, better);  // 按"谁拼在前面更大"排序

    for (int i = 0; i < n; i += 1) {
        std::cout << a[i];  // 依次拼出最大的整数
    }
    std::cout << '\n';
    return 0;
}

STL 写法

把「谁排在前面」写成一个函数对象：结构体 CmpConcat 重载 operator()，返回 x + y > y + x，再把这个规则交给 sort。它回答的不是「谁更大」，而是「两种拼接顺序哪种拼出来更大」，所以和上面按数值比较的思路完全不同；用 vector<string> 保存数字串，拼接后也不会溢出。

对应的 cppbook 章节：比较规则与函数对象

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 01:43
 * update_at: 2026-10-07 01:43
 */
// 这是 STL 写法：用 vector<string> 保存每个数，用函数对象 CmpConcat 表达
// 「谁排在前面」的拼接规则，再把这个规则交给 sort。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<string> nums; // 每个正整数按原样（字符串）保存，避免拼接后超出整数范围

// 比较规则：x 拼在 y 前面能拼出更大的数时返回 true。
// cmp(x, y) 回答的是「x 应该排在 y 前面吗」，不是「谁更大」。
struct CmpConcat {
    bool operator()(const string &x, const string &y) const {
        return x + y > y + x; // 只看两种拼接顺序哪个更大
    }
};

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

    ll n;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        string s;
        cin >> s;
        nums.push_back(s);
    }

    // 传入函数对象作为比较规则，让 sort 按「谁排在前面」重排整个 vector
    sort(nums.begin(), nums.end(), CmpConcat());

    for (ll i = 0; i < n; i++) {
        cout << nums[i];
    }
    cout << '\n';

    return 0;
}

复杂度

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

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

总结

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