2025真题 | 拼数 luogu-P14357

CSP-J 2025真题- 拼数，字符串、一维数组/排序考点，带有初级的贪心思想，适合GESP三、四级考生练习，难度⭐⭐☆☆☆，洛谷难度等级普及−。

P14357 [CSP-J 2025] 拼数

题目要求

题目描述

小 R 正在学习字符串处理。小 X 给了小 R 一个字符串 $s$，其中 $s$ 仅包含小写英文字母及数字，且包含至少一个 $1 \sim 9$ 中的数字。小 X 希望小 R 使用 $s$ 中的任意多个数字，按任意顺序拼成一个正整数。注意：小 R 可以选择 $s$ 中相同的数字，但每个数字只能使用一次。例如，若 $s$ 为 $\tt 1a01b$，则小 R 可以同时选择第 $1,3,4$ 个字符，分别为 $1,0,1$，拼成正整数 $101$ 或 $110$；但小 R 不能拼成正整数 $111$，因为 $s$ 仅包含两个数字 $1$。小 R 想知道，在他所有能拼成的正整数中，最大的是多少。你需要帮助小 R 求出他能拼成的正整数的最大值。

输入格式

输入的第一行包含一个字符串 $s$，表示小 X 给小 R 的字符串。

输出格式

输出一行一个正整数，表示小 R 能拼成的正整数的最大值。

输入输出样例 #1

输入 #1

5

输出 #1

5

输入输出样例 #2

输入 #2

290es1q0

输出 #2

92100

说明/提示

【样例 2 解释】

$s$ 包含数字 $2,9,0,1,0$。可以证明，小 R 拼成的正整数的最大值为 $92100$。

【样例 3】

见选手目录下的 $number/number3.in$ 与 $number/number3.ans$。该样例满足测试点 $9 \sim 11$ 的约束条件。

【样例 4】

见选手目录下的 $number/number4.in$ 与 $number/number4.ans$。该样例满足测试点 $20$ 的约束条件。

【数据范围】

设 $|s|$ 为字符串 $s$ 的长度。对于所有测试数据，保证：

• $1 \leq |s| \leq 10^6$；
• $s$ 仅包含小写英文字母及数字，且包含至少一个 $1 \sim 9$ 中的数字。

• 特殊性质 A：$s$ 仅包含数字。
• 特殊性质 B：$s$ 仅包含不超过 $10^3$ 个数字。

题目分析

本题要求从给定字符串中提取所有数字，并重新排列组合成一个最大的整数。

解题思路分析：

这是一个典型的贪心算法问题。想要组成的整数最大，我们需要尽可能让高位（左边）的数字更大。例如，如果有数字 9 和 1，显然 91 > 19。因此，我们的策略是：将所有提取出的数字按从大到小的顺序排列，这样组成的整数一定是最大的。

题目给出了两种常见的实现方法：

1. 桶排序/计数排序

• 由于需要处理的元素只有数字 0-9，种类非常少，我们可以使用一个大小为 10 的数组（桶）来统计每个数字出现的次数。
• 统计完成后，只需从大到小（9 到 0）遍历桶，依次输出对应数量的数字即可。

优点：时间复杂度为 $O(N)$（$N$ 为字符串长度），效率极高，不需要进行比较排序，特别适合数据量非常大的情况。

2. 直接排序

• 将字符串中的所有数字提取出来存入一个新的字符串或数组中。
• 使用标准库函数 std::sort 对其进行降序排序。

优点：代码编写简单直观，$O(N \log N)$ 的时间复杂度在题目给定的 $10^6$ 数据范围内也是完全可以通过的。

对于本题 $10^6$ 的数据量，两种方法都能轻松通过，同学们可以根据自己的习惯选择。

示例代码

方法一、字符串统计

#include <algorithm>
#include <iostream>

// P14357 [CSP-J 2025] 拼数 - 解法2：桶排序/计数排序
// 解题思路：
// 由于题目只涉及数字 0-9，我们可以统计每个数字出现的次数。
// 然后按照数字即大小（9到0）的顺序，依次输出对应数量的该数字，即可得到最大整数。
// 这种方法的时间复杂度为 O(|s|)，在数据量非常大时比直接排序 O(|s|log|s|) 更优。

int counts[15];  // 桶数组，counts[i] 表示数字 i 出现的次数
int main() {
    std::string s;
    std::cin >> s;  // 输入字符串
    std::string ans;
    // 遍历字符串 s，统计每个数字字符出现的频率
    for (int i = 0; i < s.size(); i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            counts[s[i] - '0']++;  // 将字符转换为数字索引，并增加计数
        }
    }
    // 从大到小 (9 -> 0) 遍历所有可能的数字
    for (int i = 9; i >= 0; i--) {
        // 将数字 i 重复添加 counts[i] 次到结果中
        for (int j = 0; j < counts[i]; j++) {
            ans += i + '0';  // 将整数 i 转换回字符形式
        }
    }
    std::cout << ans << std::endl;  // 输出最大整数
    return 0;
}

方法二、字符排序

#include <algorithm>
#include <iostream>

// P14357 [CSP-J 2025] 拼数
// 题目要求：从给定字符串中选出所有数字，拼成一个最大的正整数。
// 解题思路：贪心策略。为了使拼成的整数最大，我们应该尽可能让高位（左边）的数字更大。
// 因此，我们将字符串中所有的数字提取出来，然后按从大到小的顺序排列，即可得到最大整数。

int main() {
    std::string s;
    std::cin >> s;  // 输入包含字母和数字的字符串 s
    std::string ans;
    // 遍历字符串 s，筛选出所有的数字字符
    for (int i = 0; i < s.size(); i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            ans += s[i];  // 将数字字符加入到答案字符串中
        }
    }
    // 使用 std::sort 对提取出的数字进行降序排序
    // std::greater<int>() 指定排序规则为从大到小
    std::sort(ans.begin(), ans.end(), std::greater<int>());
    std::cout << ans << std::endl;  // 输出最终拼接成的最大整数
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号