[CSP-J 2025] 拼数 题解

题目分析

本题要求从给定字符串 $s$ 中提取所有数字字符，并重新排列拼接成一个最大的正整数。题目保证字符串中至少包含一个 $1 \sim 9$ 的数字。

核心观察

1. 正整数的大小比较：
   • 长度越长，正整数越大；
   • 长度相同时，高位数字越大，正整数越大。
2. 贪心选择：
   • 因为题目允许选择任意多个数字，且存在至少一个非零数字，为了让结果最大，我们必须选择所有的数字字符（每多一个数字，位数就增加一位，数字必然更大）；
   • 在确定使用所有数字后，要想让数值最大，应该把较大的数字排在更高的位上。即：将所有数字字符按照从大到小（降序）排序。

算法实现

1. 遍历字符串 $s$，将所有数字字符 '0' $\sim$ '9' 统计出现次数（桶排序 / 计数排序）或放入列表中排序。
2. 从 '9' 到 '0' 依次输出所有统计到的数字。
3. 时间复杂度为 $O(|s|)$，空间复杂度为 $O(1)$（只需长度为 10 的计数数组），完全能够在 $10^6$ 数据规模下极速通过。

参考代码 (C++)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int cnt[10];

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

    string s;
    if (!(cin >> s)) return 0;

    for (char c : s) {
        if (c >= '0' && c <= '9') {
            cnt[c - '0']++;
        }
    }

    for (int d = 9; d >= 0; --d) {
        while (cnt[d]--) {
            cout << d;
        }
    }
    cout << "\n";

    return 0;
}

参考代码 (Python 3)

import sys

def main():
    s = sys.stdin.read().strip()
    digits = [c for c in s if c.isdigit()]
    digits.sort(reverse=True)
    print("".join(digits))

if __name__ == "__main__":
    main()