[CF1799C] Double Lexicographically Minimum 题解

字典序最小化的一个一般做法就是按位确定。设

t_i

翻转后对应

t_{to_i}

，从左到右逐位确定

t

，若当前确定

t_i=c

，其中

c

是还剩有的最小字符，为了使

t

翻转后

t'_i

不变为一个更大的字符，需要尽可能使得

t_{to_i}=c

。

如果能够满足，就向两端填入

c

。否则，一个明显的想法是，设次小字符为

d

，则令

t_i=d,t_{to_i}=c

，这样保证了

t_{\max}

一定为

t

本身，然后剩下的字符从小到大从左往右填进去。

但是，设次次小字符为

e\neq d

，若

e

不存在，可以将

c

挪到字符串中央，显然这样是最优的。否则，

c

进行移动时需要在

c

曾经停留的地方放入

d

来保证还有可能使得

t_{\max}=t

，此时

e

一定会向前移动，一定不优。于是分讨这样的

e

是否存在即可。

code

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
using namespace std;
typedef unsigned long long ll;
typedef __int128 LL;
const ll maxn=200007,ee=1e18;
ll n;
string s,ans;
void solve(void){
	for(ll i=0;2*i+1<n;i++){
		if(s[2*i]==s[2*i+1]) ans[i]=ans[n-1-i]=s[2*i];
		else{
			ans[i]=s[2*i+1],ans[n-1-i]=s[2*i];
			if(2*(i+1)>=n) return;
			if(s[n-1]==s[2*i+1]){
				for(ll j=i;j<=n-1-i;j++) ans[j]=s[n-1];
				ans[n/2]=s[2*i];
				return;
			}
			for(ll j=i+1,c=2*i+2;j<n-1-i;j++,c++) ans[j]=s[c];
			return;
		}
	}
	if(n&1) ans[n/2]=s[n-1];
}
int main(void){
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	ll T=1; cin>>T;
	for(;T--;){
		cin>>s,n=s.length();
		ans.resize(n);
		sort(s.begin(),s.end());
		solve();
		cout<<ans<<"\n";
	}
	return 0;
}

[CF1799C] Double Lexicographically Minimum 题解

文章操作

相关推荐

评论

[CF1799C] Double Lexicographically Minimum 题解