CF180 D. Name

CF180 D. Name

Question

给定两个字符串 $s$s和 $t$t，若重新排列 $s$s之后能使得 $s>t$s>t，则输出字典序尽可能小且满足条件的 $s$s，否则输出 $-1$−1。

Solution

贪心+分类讨论+DFS
这里思路应该是十分清晰的，主要我在想如何实现会比较方便，看了一下当时比赛第一个交的人，交的是一份DFS，一个一个字符往下去遍历，挺适合这里的，而且也好写。
$s$s的前缀应尽可能和 $t$t一样，若 $s$s的前缀和 $t$t一样。

1. 若前缀一样且 $\mid s\mid >\mid t\mid$∣s∣>∣t∣，则可以构造出 $t+s去掉t之后剩余部分字典序最小的排列方式$t+s去掉t之后剩余部分字典序最小的排列方式
2. 若 ∣s∣<=∣t∣，则构造前缀一样，且会在某一位存在 $s_i>t_i$si​>ti​，此时后续依旧是 $s剩余部分字典序最小的排列方式$s剩余部分字典序最小的排列方式。
3. $s$s无论怎么排都无法达到上述2条，则输出"-1"。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 5e3 + 5;

char s[N],t[N];
int cnt[26],lens,lent;
string ans;

void print(){
	for(int i=0;i<26;i++)
		for(int j=0;j<cnt[i];j++)
			ans.push_back(char(i+'a'));
	cout<<ans<<'\n';
	exit(0);
}

void dfs(int x){
	if(x==lent+1){
		if(x<=lens) print();
		return;
	}
	if(x==lens+1) return;
	int num=t[x]-'a';
	if(cnt[num]>0){
		cnt[num]--;ans.push_back(t[x]);
		dfs(x+1);
		cnt[num]++;ans.pop_back();
	}
	for(int i=num+1;i<26;i++)
		if(cnt[i]>0){
			cnt[i]--;ans.push_back(char(i+'a'));
			print();
		}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>s+1>>t+1;
	lens=strlen(s+1);
	lent=strlen(t+1);
	for(int i=1;i<=lens;i++) cnt[s[i]-'a']++;
	dfs(1);
	cout<<-1<<'\n';
	return 0;
}