数字重构
给定两个正整数 $a$ 和 $b$，均不含前导 $0$。
现在，请你对 $a$ 进行重构，重新排列其各位数字顺序，得到一个不含前导 $0$ 的新正整数。
要求新正整数在不超过 $b$ 的前提下，尽可能大。
输出新正整数。
注意，我们允许新正整数等于 $a$，即保持原样不变。
输入格式
第一行包含一个正整数 $a$。
第二行包含一个正整数 $b$。
两个输入数字均不含前导 $0$。
输出格式
一个不含前导 $0$ 的正整数，表示答案。
数据保证一定有解。
数据范围
前 $6$ 个测试点满足 $1\leq a,b \leq 10^{9}$。
所有测试点满足 $1 \leq a,b \leq 10^{18}$。
输入样例1：
123 222
输出样例1：
213
输出样例2：
3921 10000
输出样例2：
9321
输入样例3：
4940 5000
输出样例3：
4940
解题思路
这题其实很简单，但是在比赛的时候没想出来，我太弱了...qwq...
这是一个很经典的贪心问题。求一个字典序最小的序列，或者是求一个最小的数，我们的贪心思路是，从最高位往低位去找，在满足条件的情况下从最大的数往小的数枚举。
比如这题，我们从最高位开始找，从$9$开始枚举，看看$9$是否满足条件，如果$9$不满足条件就看看$8$，如果$8$不满足条件就再看$7$......，以此类推。
那么我们如何判断每一位选的数是否满足条件呢？首先这个数是可以选到的，同时选了这个数后，前面的位已经固定，后面的位应该存在一种摆法，使得$a \leq b$。要判断$a \leq b$，可以判断后面的最小摆法（后面的位按数字递增摆）小于等于$b$，即$a_{min} \leq a \leq b$。
AC代码如下：
1 #include <cstdio>
2 #include <iostream>
3 #include <string>
4 #include <algorithm>
5 using namespace std;
6
7 int cnt[10];
8
9 string get_min(int n) {
10 string ret = to_string(n);
11 cnt[n]--;
12
13 for (int i = 0; i <= 9; i++) {
14 for (int j = 0; j < cnt[i]; j++) {
15 ret += to_string(i);
16 }
17 }
18
19 cnt[n]++;
20
21 return ret;
22 }
23
24 int main() {
25 string a, b;
26 cin >> a >> b;
27
28 // 把a的每位数字取出来
29 for (int i = 0; i < a.size(); i++) {
30 cnt[a[i] - '0']++;
31 }
32
33 // 如果a的位数小于b，a能取到最大的数就是按递减的顺序排
34 if (a.size() < b.size()) {
35 sort(a.begin(), a.end(), greater<char>());
36 cout << a;
37 }
38 else {
39 string ret;
40 for (int i = 0; i < a.size(); i++) { // 从最高位开始找
41 int j = 9; // 每一位从9开始枚举
42 // 找到一个数，这个数要存在，同时后面的最小摆法要小于b
43 while (cnt[j] == 0 || ret + get_min(j) > b) {
44 j--;
45 }
46 ret += to_string(j);
47 cnt[j]--;
48 }
49 cout << ret;
50 }
51
52
53 return 0;
54 }
参考资料
AcWing 4307. 数字重构（AcWing杯 - 周赛）：https://www.acwing.com/video/3719/