24. 重新排列
题目ID：20009拓展题100分
最新提交：
Time Limit Exceeded
40 分
历史最高：
Time Limit Exceeded
40 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
给出两个正整数a,b。在十进制下重排a，构造一个不超过b的最大数，不能有前导零。允许不去重排a。
输入格式
第一行一个数a (1≤a≤10181≤a≤1018)。第二行一个数b (1≤b≤10181≤b≤1018)
数没有前导零，数据保证有解。
输出格式
输出一个数，表示a重排后不超过b的最大数，不应该有前导零。
输出的数的长度应该与a相等，它应该是a的一个排列。
样例
Input 1
123 222
Output 1
213
Input 2
3921 10000
Output 2
9321
Input 3
4940 5000
Output 3
4940
#include<bits/stdc++.h>
using namespace std;
bool b[21];
bool cmp(char x,char y){
return x>y;
}
bool cheak(string x,string y){
if(x.size()==y.size()){
for(int i=0;i<x.size();i++){
if(x[i]!=y[i]){
return x[i]>y[i];
}
}
return true;
}
return x.size()>y.size();
}
string x,y,cnt,ans;
void dfs(int num,bool bb){
if(num==x.size()+1){
if(cheak(y,ans)&&cheak(ans,cnt)){
cnt=ans;
}
return;
}
for(int i=0;i<x.size();i++){
if((x[i]<=y[num-1]||bb)&&b[i]==0){
b[i]=1;
ans.push_back(x[i]);
dfs(num+1,bb||x[i]<y[num-1]);
ans.pop_back();
b[i]=0;
if(x[i]<y[num-1])break;
}
}
}
int main(){
cin>>x>>y;
sort(x.begin(),x.end(),cmp);
if(y.size()>x.size()){
cout<<x;
return 0;
}
dfs(1,0);
cout<<cnt;
return 0;
}
复制到c++就好了，我不知道咋格式化
