P14357 [CSP-J 2025] 拼数 / number

Nancy_Cherry · 2025-11-01 16:42:04 · 题解

P14357 [CSP-J 2025] 拼数 / number 题解

题目分析

题目要求我们从给定的字符串中提取数字字符，然后使用这些数字字符拼成最大的正整数。每个数字字符只能使用一次，且不能有前导零。

解题思路

要组成最大的正整数，应该从字符串中提取所有数字字符，将这些数字字符按从大到小排序，并且确保结果是一个正整数（不能以 0 开头）

算法实现

遍历字符串，收集所有数字字符,对收集到的数字字符按从大到小排序, 将排序后的字符连接成字符串输出。

代码实现

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    string s;
    cin >> s;

    // 提取所有数字字符
    string d = "";
    for (char c : s) {
        if (c >= '0' && c <= '9') {
            d += c;
        }
    }

    // 按从大到小排序
    sort(d.begin(), d.end(), greater<char>());

    // 输出结果
    cout << d << endl;

    return 0;
}

算法分析

• 时间复杂度：O(n log n)，其中n是字符串长度。主要时间消耗在排序上。
• 空间复杂度：O(n)，用于存储提取的数字字符。

主要考察字符串处理和排序的基本能力。