题解

#include<bits/stdc++.h>
using namespace std;

int n;
int num[1005];
int f_min[1005];//find_min，f_min[i]表示i右侧能找到的最小数
set<int> g[1005];//用set来建图
int color[1005];//记录染色的情况，用1和2代表颜色
int cnt1,cnt2;

bool bfs(int s){//s是起点
queue<int> q;
q.push(s);
color[s]=1;
while(!q.empty()){
int a=q.front();
q.pop();
for(auto i=g[a].begin();i!=g[a].end();i++){
if(!color[(*i)]){//没染过色
color[(*i)]=3-color[a];
q.push((*i));
}
else if(color[(*i)]==color[a]){//染色出现矛盾
return false;
}
}
}
return true;
}

void push_and_pop(){
stack<int> st1,st2;
int it=1;
for(int i=1;i<=n;i++){//i表示当前应当输出的数字
if((!st1.empty())&&st1.top()i){
printf("b ");
st1.pop();
}
else if((!st2.empty())&&st2.top()i){
while(num[it]!=i+1&&it<=n){//在进行d操作之前尽量多地进行a操作
int x=color[it];
if(x1){
st1.push(num[it]);
printf("a ");
}
else if(x2){
break;
st2.push(num[it]);
printf("c ");
}
it++;
}
if(color[it]1){//特判，把i-1这个数放进stack1
st1.push(num[it]);
printf("a ");
it++;
}
printf("d ");
st2.pop();
}
else{
while(num[it]!=i&&it<=n){
int x=color[it];
if(x1){
st1.push(num[it]);
printf("a ");
}
else if(x==2){
st2.push(num[it]);
printf("c ");
}
it++;
}
printf("a b ");
it++;
}
}
}

int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&num[i]);
}
for(int i=1;i<n;i++){
int t=num[i];
for(int j=i+1;j<=n;j++){
t=min(t,num[j]);
}
f_min[i]=t;
}
for(int i=1;i<n;i++){
for(int j=i+1;j<n;j++){
if(num[i]<num[j]){
if(f_min[j]<num[i]){
g[i].insert(j);
g[j].insert(i);//建无向图
}
}
}
}
for(int i=1;i<=n;i++){
if(!color[i]){
bool f=bfs(i);
if(!f){
printf("0");
return 0;
}
}
}
for(int i=1;i<=n;i++){
if(color[i]==2)cnt2++;
else cnt1++;
}
if(cnt2>cnt1){//让染完色后数量多的一方使用A栈
for(int i=1;i<=n;i++){
if(color[i]==2)color[i]=1;
else color[i]=2;
}
}
push_and_pop();
return 0;
}
加粗文本