题解 牛客练习赛116 C排序

如果把数码 排成一圈，则 和 可以交换需要满足 和 相邻．可以发现一个位置可以挪动到第一个位置的条件是前面位置的数码都与其相邻．那我们不妨考虑这样构造答案序列：每次选择一个位置将其移动到开头，直到将所有位置选择完．可以发现：

• 初始时若有 ，则之后不论怎么调整， 都在 的前面．即终止情况 必然会在 之前．反映到我们的构造方案上， 一定会先挪动到开头．
• 每次只能将某个数码最靠近前面的位置移到第一个位置，因为其余的位置在其之前有相同的数码，不符合相邻的条件．

不妨动态维护 每个数码第一次出现的位置．每次贪心地选择最小的可操作数码挪到第一个位置，然后更新这个数码最靠前的位置．这时如果每次暴力检查若干数码是否合法，总复杂度为 ，比较难以通过．考虑维护数码第一次出现位置的前后缀 ，每次更新答案之后暴力修改，总复杂度可以降为 ．

code：

#include<bits/stdc++.h>
#define pii pair<int, int>
#define fr first
#define sc second
using namespace std;
inline int rd(void){
	int s=0, f=1; char c=getchar();
	while(c<'0' || c>'9') {if(c=='-') f=0; c=getchar();}
	while(c>='0' && c<='9') {s=s*10+c-'0'; c=getchar();}
	return f? s:-s;
}

const int N=1e7+5;
int n, a[N], nxt[N], pos[10], ans[N];
int pmn[10], smn[10], mn0, mn9;

inline void rebuild(){
	pmn[0]=pos[0]; for(int i=1; i<10; i++) pmn[i]=min(pmn[i-1], pos[i]);
	smn[9]=pos[9]; for(int i=8; ~i; i--) smn[i]=min(smn[i+1], pos[i]);
	mn9=n+1; for(int i=1; i<=7; i++) mn9=min(mn9, pos[i]);
	mn0=n+1; for(int i=2; i<=8; i++) mn0=min(mn0, pos[i]);
}

inline bool check(int i){
	if(pos[i]==n+1) return false;
	if(i==0) return mn0>pos[i];
	if(i==9) return mn9>pos[i];
	int x=n+1;
	if(i>1) x=min(x, pmn[i-2]);
	if(i<8) x=min(x, smn[i+2]);
	return x>pos[i];
}

void solve(){
	static char str[N];
	scanf("%s", str+1);
	n=strlen(str+1); for(int i=1; i<=n; i++) a[i]=str[i]-'0';
	
	for(int i=0; i<10; i++) pos[i]=n+1;
	for(int i=n; i; i--) nxt[i]=pos[a[i]], pos[a[i]]=i;
	
	rebuild();
	for(int i=1; i<=n; i++){
		for(int j=0; j<10; j++) if(check(j)){
			ans[i]=j;
			pos[j]=nxt[pos[j]];
			rebuild();
			break;
		}
	}
	for(int i=1; i<=n; i++) printf("%d", ans[i]);
	puts("");
}

signed main(){
	int T=rd();
	while(T--){
		solve();
	} 
	return 0;
}