【CSP-J 2025T1】拼数 详细解析
本帖最后由 高山 于 2026-9-24 18:59 编辑如果你正在复习CSP-J 第二轮
那你可以按照本系列的节奏进行
在本系列中，我们将带领鱼油一同回顾算法基础，完成CSP算法真题，帮助他们尽可能在复赛获得更高的分数。1
话不多说，让我们先看看题目：
static/image/hrline/line1.png
可使用配套的在线OJ评测本题->
static/image/hrline/line1.png
static/image/hrline/line1.png
P14357 拼数
小 R 正在学习字符串处理。小 X 给了小 R 一个字符串 s，其中 s 仅包含小写英文字母及数字，且包含至少一个 1～9 中的数字。小 X 希望小 R 使用 s 中的任意多个数字，按任意顺序拼成一个正整数。
注意：小 R 可以选择 s 中相同的数字，但每个数字只能使用一次。
例如，若 s 为 1a01b，则小 R 可以同时选择第 1、3、4 个字符，分别为 1、0、1，拼成正整数 101 或 110；但小 R 不能拼成正整数 111，因为 s 仅包含两个数字 1。
小 R 想知道，在他所有能拼成的正整数中，最大的是多少。你需要帮助小 R 求出他能拼成的正整数的最大值。
【输入格式】
输入的第一行包含一个字符串 s，表示小 X 给小 R 的字符串。
【输出格式】
输出一行一个正整数，表示小 R 能拼成的正整数的最大值。
【输入输出样例】
输入 #1
29010
输出 #1
92100
【样例 1 说明】
s 包含数字 2、9、0、1、0。可以证明，小 R 拼成的正整数的最大值为 92100。
输入 #2
1a01b
输出 #2
110
【数据范围】
设 |s| 为字符串 s 的长度。对于所有测试数据，保证：
[*]1 ≤ |s| ≤ 1 000 000
[*]s 仅包含小写英文字母及数字字符 0～9
[*]s 包含至少一个 1～9 中的数字
【特殊性质】
特殊性质 A：字符串 s 中只包含数字字符。
特殊性质 B：字符串 s 中数字字符的个数不超过 1000。
点击目录的「解析」按钮或点击下一页即可查看答案。如您
满分代码：
**** Hidden Message *****
本题所在OJ用到的测试点信息：
本题所使用的测试点生成程序（运行gen.cpp）
贪心原理图：
以下是解析，部分由AI生成
P14357 拼数 —— 一步一步理解贪心原理
一、题目到底要我们做什么？
给一个字符串，里面混着小写字母和数字。我们要从里面挑出一些数字，按任意顺序拼成一个正整数，让这个数尽量大。
关键理解：每个字符只能用一次（挑走了就没了），但可以挑相同的数字，只要原串里确实有这么多。
例子：s = 2 9 0 1 0，里面有数字 {2, 9, 0, 1, 0}，能拼出的最大数是 92100。
二、核心思考：什么样的数最大？
比较两个正整数的大小，规则是：先看位数，位数多的更大；位数一样，再看高位，高位大的更大。
这就给了我们两个贪心方向：
[*]位数越多越好 —— 所以只要能用上的数字，统统用上（0 也不例外，放在末尾只会增加位数）
[*]高位越大越好 —— 所以数字要从大到小、从高到低依次放
结论：把所有数字从 9 到 0 排下来，就是答案。
以 2 9 0 1 0 为例：从 9 开始放 → "9"，再放 2 → "92"，再放 1 → "921"，最后放两个 0 → "92100"。
三、那字母怎么办？
字母不是数字，根本不能拿来拼数，所以对答案没有任何影响。
处理方法：遍历字符串时，遇到字母直接跳过（ignore），只处理数字。这就是 isdigit 的作用。
例子：s = 1a01b，挑出来的数字还是 {1, 0, 1}，答案是 110，字母 a、b 完全不参与。
四、具体实现分两步
第一步：统计每个数字出现了几次
开一个大小为 10 的数组 cnt，cnt 表示数字 i 出现的次数。
for (int i = 0; i < s.size(); i++) {
if (isdigit(s<i>)) { // 是数字才处理
int d = s<i> - '0'; // 字符转数字：'0'->0, '1'->1 ... '9'->9
cnt++; // 对应计数器 +1
}
}
小技巧：s - '0' 是把字符变数字的核心写法，一定要记住。
第二步：从大到小把数字拼起来
string ans;
for (int i = 9; i >= 0; i--) { // 从 9 数到 0
ans += string(cnt, '0' + i); // 把数字 i 重复 cnt 次接在末尾
}
cout << ans << endl;
string(cnt, '0'+i) 的意思是：生成一个由 cnt 个字符 '0'+i 组成的字符串，比如 cnt=2 就生成 "00"。
五、几个易错点提醒
[*]答案不能用 int / long long 存 —— 数字可能长达 1 000 000 位，只能用 string
[*]cnt 数组要开 10 —— 下标 0~9 正好对应 10 个数字，别开小了
[*]循环用 < 不要用 <= —— s.size() 的位置是字符串结尾，访问会越界
[*]记得输出 —— 拼完 R 后别忘了 cout，不然交上去是 0 分
[*]养成关同步的习惯 —— ios::sync_with_stdio(false); cin.tie(0); 大输入必写
六、复杂度分析
[*]时间复杂度：O(|s|)，遍历一次字符串，再遍历固定 10 个数字
[*]空间复杂度：O(|s|)，答案串最长就是所有数字都用上
一句话记住这道题：统计频次，从 9 到 0 依次拼，字母直接跳过，答案用 string 存。
鱼油你好，这道题是典型的贪心 + 计数题。核心一句话：把所有数字从大到小拼起来，就是最大正整数。
一、为什么这样贪心？
比较两个正整数：
1. 先比位数，位数多的更大。
2. 位数相同，再比高位，高位大的更大。
所以：
- 能用的数字全用上，0也放末尾，这样位数最多。
- 数字从9到0依次放，保证高位尽量大。
- 字母不能拼数，直接跳过。
例如 29010 中有 2、9、0、1、0，从大到小排就是 92100。
二、实现步骤
1. 开一个 cnt 数组，统计数字 0～9 各出现几次。
2. 遍历字符串，遇到数字字符就 cnt - '0']++。
3. 从 9 到 0，把数字 i 重复 cnt 次接到答案后面。
4. 输出答案字符串。
三、完整满分代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
string s;
cin >> s;
int cnt = {0};
for (char c : s) {
if (isdigit(c)) {
cnt++;
}
}
string ans;
for (int i = 9; i >= 0; i--) {
ans += string(cnt, char('0' + i));
}
cout << ans << '\n';
return 0;
}
四、复杂度
时间复杂度：O(|s| + 10)
空间复杂度：O(1)（不计输出字符串）
数据范围 |s| ≤ 1 000 000，完全可以通过。
五、易错点
- 字母必须跳过，不能参与拼数。
- s - '0' 是把字符变成数字的关键写法。
- 0 放最后不会产生前导零，因为题目保证至少有一个 1～9 的数字。
- 用 string(cnt, '0' + i) 可以快速生成重复字符。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 点了点了 {:7_146:} {:5_106:} {:7_146:} {:7_146:}
页:
[1]