最大整数

题目描述

给定 $n$ 个正整数，把它们首尾相接拼成一个多位整数，求最大可能值。

输入：第一行 $n$ ，第二行 $n$ 个正整数。输出：拼接后的最大数。

样例： $13\ 312\ 343$ 拼成 $34331213$ 。

思路

对任意两数 $a,b$ ，若 $ab>ba$ 则 $a$ 应排在 $b$ 前。按此规则排序后顺次拼接即得最优解。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-02 19:18
# update_at: 2026-10-04 10:36

import sys
from functools import cmp_to_key


def bigger_first(a: str, b: str) -> int:
    """拼接比较器：a 放在 b 前拼出的数更大时返回负数，让 sort 产出最大拼接。"""
    ab, ba = a + b, b + a
    if ab > ba:
        return -1
    return 1 if ab < ba else 0


def solve() -> None:
    data = iter(sys.stdin.read().split())
    n = int(next(data))                    # 数字个数，n < 20
    nums = [next(data) for _ in range(n)]  # 保留字符串：拼接按位比较，转 int 反而丢掉顺序信息
    nums.sort(key=cmp_to_key(bigger_first))  # 比较器等价于键 x/(10^len-1) 降序，全序保证贪心最优
    print(''.join(nums))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-06 02:11
 * update_at: 2026-10-06 02:11
 */
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 25;

string a[MAXN]; // 每个数字保留为字符串，方便拼接比较

// 比较器：a 放在 b 前面拼出的数更大时返回 true，用于按最大拼接排序
bool cmp(const string &a, const string &b) {
    return a + b > b + a;
}

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

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

    sort(a, a + n, cmp); // 按拼接后的字典序降序排列

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

    return 0;
}

目录

题目描述

思路

参考代码