C++ 解法, 执行用时: 6ms, 内存消耗: 2312K, 提交时间: 2022-01-04 21:29:38

#include<bits/stdc++.h>
using namespace std;
int s[1001],f[1001],color[1001],edge[1001][1001],n;
stack<int> a,b;
queue<char> q;
void dfs(int x,int c){
	color[x]=c;
	for(int i=1;i<=n;i++)if(edge[x][i]){if(color[i]==c)cout<<0,exit(0);if(!color[i])dfs(i,3-c);}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>s[i];
	f[n+1]=0x7fffffff;
	for(int i=n;i>0;i--)f[i]=min(s[i],f[i+1]);
	for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)if(s[i]<s[j]&&f[j+1]<s[i])edge[i][j]=edge[j][i]=1;
	for(int i=1;i<=n;i++)if(!color[i])dfs(i,1);
	for(int i=1,j=1;i<=n;i++){
		if(color[i]==1)a.push(s[i]),q.push('a');
		else b.push(s[i]),q.push('c');
		while((!a.empty()&&a.top()==j)||(!b.empty()&&b.top()==j)){
			if(!a.empty()&&a.top()==j)a.pop(),q.push('b'); 
			else b.pop(),q.push('d');
			j++;	
		}
	}	
	while(!q.empty())cout<<q.front()<<" ",q.pop();
	return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 57ms, 内存消耗: 20292K, 提交时间: 2020-08-29 01:08:42

#!/usr/bin/env python3
#
# 双栈排序
#
# import sys, os

def read_int(): return int(input())
def read_ints(): return list(map(int, input().split()))

n = read_int()
a = read_ints()[::-1]
s1, s2 = [], []

def check():
	if not s2: return True
	for i in range(len(a) - 2, -1, -1):
		if a[i] > a[-1] and a[i] > s2[-1]:
			for j in range(i - 1, -1, -1):
				if a[j] < a[-1]: return False
			break
	return True

ans = []
c = 0
while c < n:
	if a and (not s1 or s1[-1] > a[-1]) and check():
		s1.append(a.pop())
		ans.append('a')
		continue
	if s1 and s1[-1] == c + 1:
		s1.pop()
		ans.append('b')
		c += 1
		continue
	if a and (not s2 or s2[-1] > a[-1]):
		s2.append(a.pop())
		ans.append('c')
		continue
	if s2 and s2[-1] == c + 1:
		s2.pop()
		ans.append('d')
		c += 1
		continue
	break

if c == n:
	print(" ".join(ans))
else:
	print(0)

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 484K, 提交时间: 2020-09-28 19:22:54

#include<bits/stdc++.h>
using namespace std;
stack<int> s1,s2;
int n,a[1005],cur=1,l=1;
string s;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	while(cur<=n){		
	    if(a[l]==cur){s+="a b ";cur++,l++;}
		else if(!s1.empty()&&s1.top()==cur){s1.pop();s+="b ";cur++;}
		else if(!s2.empty()&&s2.top()==cur){s2.pop();s+="d ";cur++;}
	    else if(!s1.empty()&&s1.top()==a[l]+1){s1.push(a[l]);s+="a ";l++;}
		else if(!s2.empty()&&s2.top()==a[l]+1){s2.push(a[l]);s+="c ";l++;}
		else if(s1.empty()||s1.top()>a[l]){s1.push(a[l]);s+="a ";l++;}
		else if(s2.empty()||s2.top()>a[l]){s2.push(a[l]);s+="c ";l++;}
		else{printf("0\n");return 0;}
	}
	cout<<s<<endl;
	return 0;
}