题意简述
有两个 \(n\) 位十进制数 \(a\)，\(b\)。要将数字 \(b\) 的每一位重新排列后，使得得到的数字一个在大于等于 \(a\) 的情况下更接近 \(a\)，另一个在小于 \(a\) 的情况下更接近 \(a\)。
求这两个数，如果找不到就输出 0。
思路
以大于等于 \(a\) 的为例。
我们可以将 \(b\) 从小到大排序，然后深搜搜出两个数字，我是分开搜的。
假设现在搜到第 \(x\) 位。
-
如果搜的数第 \(x\) 位前面已经比 \(a\) 第 \(x\) 位大，则尽量选小的。
-
如果没有，则必须要一个大于等于 \(a\) 这一位的数，而这个数也要尽量小，而 \(b\) 是已经排好序了的，所以从前往后遍历第一次是最小的。
当 \(x\) 等于 \(n\)，也就是最后一位也搜完了。
-
如果 \(x\) 大于等于 \(a\)，第一次搜到的肯定是优的，因为每次都尽量选小的嘛，所以就找到答案，则用一个变量来标记找到了，其他的就不用继续搜了。
-
如果不满足就让其他继续搜。
以上是求大于等于 \(a\) 的数的思路，另一个数同理。
AC CODE
#include<bits/stdc++.h>
using namespace std;
#define int long long
string ans1="",ans2="",stra,strb;
int vis[1000];
bool ok=0;
int bijiao(string a,string b){
if(a==b)return 0;
if(a<b)return 1;
return 2;
}
void dfs(bool b,string f){
if(f.size()==strb.size()){
if(bijiao(f,stra)==2||bijiao(f,stra)==0&&f[0]!='0')ans2=f,ok=1;
return;
}
if(ok)return;
if(b){
for(int i=0;i<strb.size();i++){
if(!vis[i]){
vis[i]=1;
dfs(b,f+strb[i]);
vis[i]=0;
}
}
}
else{
for(int i=0;i<strb.size();i++){
if(!vis[i]&&strb[i]>=stra[f.size()]){
vis[i]=1;
dfs(strb[i]>stra[f.size()],f+strb[i]);
vis[i]=0;
}
}
}
}
void dfs2(bool b,string f){
if(f.size()==strb.size()){
if(bijiao(f,stra)==1&&f[0]!='0')ans1=f,ok=1;
return;
}
if(ok)return;
if(b){
for(int i=0;i<strb.size();i++){
if(!vis[i]){
vis[i]=1;
dfs2(b,f+strb[i]);
vis[i]=0;
}
}
}
else{
for(int i=0;i<strb.size();i++){
if(!vis[i]&&strb[i]<=stra[f.size()]){
vis[i]=1;
dfs2(strb[i]<stra[f.size()],f+strb[i]);
vis[i]=0;
}
}
}
}
signed main(){
cin>>stra;cin>>strb;
sort(strb.begin(),strb.end());
ok=0;
dfs(0,"");
ok=0;
reverse(strb.begin(),strb.end());
dfs2(0,"");
//这些if大部分没用
if(ans2==""||(ans2.size()&&ans2[0]=='0'))cout<<0<<endl;
else cout<<ans2<<endl;
if(ans1==""||(ans1.size()&&ans1[0]=='0')||ans1==stra)cout<<0<<endl;
else cout<<ans1<<endl;
return 0;
}