算法分析

(二分图,栈,染色法,贪心) O($n^2$)

如果只有一个栈，则整个操作顺序是固定的：

从前往后遍历每个数，每次先将当前数压入栈中，如果后面的所有数均比栈顶元素大，则将栈顶弹出，否则栈顶不能被弹出。

因此，我们只需考虑将每个数分配给哪个栈即可。

这里有个很强的性质：两个数 $i,j(i≤j)$不能被放入同一个栈中，当且仅当存在 $k$,$k>j$ , 且 $q[k]<q[i]<q[j]$。

证明： 必要性： 如果有 $i < j < k$, 且 $q[k] < q[i] < q[j]$，则因为 $q[i]$ 和 $q[j]$ 的后面均存在一个更小的$q[k]$，因此$q[i]$和$q[j]$都不能从栈中被弹出，所以从栈底到栈顶的元素就不是单调的降序了，那么弹出时得到的序列就会出现逆序对。因此$q[i]$和$q[j]$不能被分到同一个栈中。

充分性： 如果$q[i]$和$q[j]$不满足上述条件，则我们在操作过程中一定不会出现矛盾。

在操作过程中，如果当前要入栈的数是$q[j]$，那么此时：所有大于$q[j]$的元素，都一定在栈中； 所有小于$q[j]$的元素，比如$q[i] < q[j]$，则由于后面不存在$q[k] < q[i]$，因此$q[i]$一定已经出栈；

所以此时将$q[j]$压入栈中后，从栈底到栈顶仍然可以保持降序，因此整个进栈、出栈过程是可以顺利进行的。

有了上述性质后，我们只需将所有满足条件的点分到两个栈中去即可。这一步可以转化成图论问题：

如果$i, j$满足条件，则在i和j之间连一条边。 然后判断是否是二分图即可。

输出字典序最小的方案 答案要求字典序最小，因此从前往后染色时，需要优先将当前点分配到第一个栈中。

另外对于每一个栈，操作序列是唯一确定的，也就是ab的相对顺序是固定的，且cd的相对顺序也是固定的。

另外在最优解中，每个数插入哪个栈中也是唯一确定的，所以ac的相对顺序也固定。

最后，输出序列是唯一确定的，所以bd的相对顺序也固定。

所以在最终方案中，只有ad、bc的相对顺序可变，所以我们只需先随便求一个方案，然后将所有连续的bc区间排序，以及连续的ad区间排序即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n;
int a[N],f[N];
bool g[N][N];
int color[N];
bool dfs(int u,int c) //染色法判定二分图
{
	color[u]=c;
	for(int j=1;j<=n;j++)
	{
		if(!g[u][j]) continue; //没有边
		if(color[j])
		{
			if(color[j]==c)	return false; //颜色出现冲突 
		} 
		else if(!dfs(j,3-c)) return false; //染对应的颜色 
	}
	return true;//染色出现冲突 
}
bool check(char a,char b) //属于一段没有前后顺序要求的序列
{
	if(a==b) return true;
	if(a>b) swap(a,b);
	return a=='b'&&b=='c'||a=='a'&&b=='d';
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	f[n+1]=n+1;
	for(int i=n;i;i--) //处理从i开始的最小值 
	{
		f[i]=min(a[i],f[i+1]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(a[i]<a[j]&&f[j+1]<a[i]) 
			{
				g[i][j]=g[j][i]=true;//i和j不能放入同一个栈中 
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!color[i]&&!dfs(i,1)) //没有颜色且在染色的过程中出现冲突 
		{
			puts("0");
			return 0;
		}
	}
	string res;
	stack<int> stk1,stk2;
	for(int i=1,cur=1;i<=n;i++) //模拟序列
	{
		if(color[i]==1) stk1.push(a[i]),res+='a'; //放入第一个栈
		else stk2.push(a[i]),res+='c'; //放入第二个栈中
		
		while(stk1.size()&&stk1.top()==cur||stk2.size()&&stk2.top()==cur) //可以出战序列
		{
			if(stk1.size()&&stk1.top()==cur) stk1.pop(),cur++,res+='b';
			else stk2.pop(),cur++,res+='d';
		}
		
	}
	
	for(int i=0;i<res.size();i++) //枚举可交换区间进行排序
	{
		int j=i;
		while(j<res.size()&&check(res[i],res[j])) j++;
		j--;
		sort(res.begin()+i,res.begin()+j+1);
		i=j;
	}
	
    for(auto x:res) //输出最后的结果
    {
        cout<<x<<" ";
    }
	return 0;
}