2025 拼数 · 方案一收集后降序排序

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 1/5 · 共 755 字

所有数字都用上，大的排前面

2025
字符串

正文

// CSP-J 2025 复赛 T1 · 拼数
// 原题：https://oj.yecheng.tv/p/CSP2025JA
// 题意：给一个只含小写字母和数字的字符串，从中挑出若干个数字
// （同一个位置上的数字只能用一次），按任意顺序拼成一个正整数，问能拼出的最大值。
// 题目保证至少有一个 1~9 的数字。
//
// 方案一 · 收集所有数字，从大到小排序
// 想清楚一件事：位数越多数值越大，所以所有数字都要用上（0 也用，只要不排在开头）；
// 位数固定时，把大的数字放前面数值最大。所以答案就是把所有数字按降序排一遍。
// 因为题目保证有 1~9 的数字，降序之后第一位一定不是 0，天然没有前导零。
// 复杂度 O(|s| log |s|)，|s| 最多 1e6，排序也很快。

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);

    string s;
    cin >> s;

    string digits;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] >= '0' && s[i] <= '9') digits += s[i];
    }
    sort(digits.begin(), digits.end(), greater<char>());

    cout << digits << "\n";
    return 0;
}

2025 拼数 · 方案一 收集后降序排序

正文

CSP-J 标程 · 复赛真题的其它内容

2025 拼数 · 方案一收集后降序排序