统计字符串中的所有数字并按从大到小输出，最大正整数一定使用全部数字。
OJ: luogu
题目 ID: P14357
难度:入门
标签:字符串贪心计数
日期: 2026-07-05 21:24
题意
给定一个只包含小写字母和数字的字符串 s，其中至少有一个 1 到 9 的数字。
可以从字符串中选择任意多个数字，每个数字最多使用一次，并任意调整顺序，拼成一个正整数。要求输出能拼出的最大正整数。
思路
先看一个可以直接验证想法的朴素解：
cpp
// brute.cpp：小数据暴力解，枚举选择哪些数字，再排序成最大数字。
#include <bits/stdc++.h>
using namespace std;
bool better(const string &a, const string &b) {
if (a.size() != b.size()) {
return a.size() > b.size();
}
return a > b;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
string digits = "";
for (int i = 0; i < (int)s.size(); i++) {
if ('0' <= s[i] && s[i] <= '9') {
digits += s[i];
}
}
int n = (int)digits.size();
string best = "";
for (int mask = 1; mask < (1 << n); mask++) {
string cur = "";
bool has_non_zero = false;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
cur += digits[i];
if (digits[i] != '0') {
has_non_zero = true;
}
}
}
if (!has_non_zero) {
continue;
}
sort(cur.begin(), cur.end(), greater<char>());
if (better(cur, best)) {
best = cur;
}
}
cout << best << '\n';
return 0;
}下面是另一种「01 序列」风格的暴力写法。它按每个数字依次决定选或不选，递归生成完整选择后，叶子节点统一检查是否至少选了一个非零数字，并统计当前能组成的最大数：
另一种暴力写法：01 序列
cpp
// brute_01_style.cpp：01 序列风格暴力，按每个数字决定选或不选。
#include <bits/stdc++.h>
using namespace std;
string digits;
vector<int> choose_digit; // choose_digit[i] = 0/1，表示第 i 个数字不选/选
string best_answer;
bool better(const string &a, const string &b) {
if (a.size() != b.size()) {
return a.size() > b.size();
}
return a > b;
}
bool check() {
for (int i = 0; i < (int)digits.size(); i++) {
if (choose_digit[i] == 1 && digits[i] != '0') {
return true;
}
}
return false;
}
string calc_answer() {
string candidate = "";
for (int i = 0; i < (int)digits.size(); i++) {
if (choose_digit[i] == 1) {
candidate.push_back(digits[i]);
}
}
sort(candidate.begin(), candidate.end(), greater<char>());
return candidate;
}
void dfs_choose(int pos) {
if (pos == (int)digits.size()) {
if (!check()) {
return;
}
string candidate = calc_answer();
if (better(candidate, best_answer)) {
best_answer = candidate;
}
return;
}
// 第 pos 个数字的 01 选择：0 不使用，1 使用。
for (int i = 0; i <= 1; i++) {
choose_digit[pos] = i;
dfs_choose(pos + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
for (int i = 0; i < (int)s.size(); i++) {
if ('0' <= s[i] && s[i] <= '9') {
digits.push_back(s[i]);
}
}
choose_digit.assign(digits.size(), 0);
dfs_choose(0);
cout << best_answer << '\n';
return 0;
}brute.cpp 对小数据枚举选择哪些数字，再把选出的数字从大到小排序，取最大的结果。这个做法能帮助我们确认两个关键点：
- 拼出的整数位数越多，通常越大；
- 在位数相同的情况下，高位数字越大，整数越大。
由于题目保证至少存在一个非零数字，所以把所有数字都用上一定不会得到非法的 0，而且多用一个数字会让位数增加，结果不会变小。
于是正解非常直接：
- 扫描字符串，统计
0到9每个数字出现了多少次； - 从
9到0依次输出每个数字。
例如 290es1q0 中的数字是 2, 9, 0, 1, 0，按从大到小排列就是 92100。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
int cnt[10]; // cnt[d] 表示数字 d 在字符串中出现的次数
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
for (int i = 0; i < (int)s.size(); i++) {
if ('0' <= s[i] && s[i] <= '9') {
cnt[s[i] - '0']++;
}
}
// 为了得到最大的正整数，应使用所有数字，并按从大到小排列。
for (int d = 9; d >= 0; d--) {
for (int i = 1; i <= cnt[d]; i++) {
cout << d;
}
}
cout << '\n';
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
，只需要 10个计数器。
总结
本题的贪心依据是“先让位数尽量长，再让高位尽量大”。因此所有数字都要使用，并且按从大到小排列。