【NOIP2008】双栈排序 – 徐亦轲的博客

本来天真地以为是个模拟：怎么这一年都是两分钟写完的水题

然后发现错了

于是听说有这么个规律：若存在i<j<k且a[k]<a[i]<a[j]则i和j不能被加入同一个栈

这个也很好理解：若两个数，小的先加入某个栈，大的也要加入那个栈，那么小的肯定要先出栈；那么小的出栈就要保证比这个数小的数已经全部出栈了；则若存在一个比它更小的数还没有入栈那么这个数肯定还不能出栈。。大的那个数也就不能进入了。

知道了每个数要进入哪个栈然后再模拟就可以了233

// <twostack.cpp> - 02/29/16 22:12:20
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
const int MAXN=1002;
stack <int> k[2];
queue <int> q;
int a[MAXN],c[MAXN],st[MAXN];
vector <int> b[MAXN];
void color(int x){
	for(int i=0;i<b[x].size();i++){
		int next=b[x][i];
		if(st[next])continue;
		st[next]=-st[x];
		color(next);
	}
}
int main(){
	freopen("twostack.in","r",stdin);
	freopen("twostack.out","w",stdout);
	int n=getint();
	for(int i=1;i<=n;i++)a[i]=getint();
	c[n]=a[n];
	for(int i=n-1;i;i--)c[i]=min(c[i+1],a[i]);
	for(int i=1;i<n-1;i++)
		for(int j=i+1;j<n;j++)
			if(a[i]<a[j]&&c[j+1]<a[i]){b[i].push_back(j);b[j].push_back(i);}
	for(int i=1;i<=n;i++)if(!st[i]){st[i]=1;color(i);}
	int now=1,c=1;
	while(q.size()!=n<<1){
		if(now<=n&&st[now]==1&&(k[0].empty()||a[now]<k[0].top())){
			k[0].push(a[now++]);
			q.push(0);
		}else if(!k[0].empty()&&k[0].top()==c){
			k[0].pop();c++;
			q.push(1);
		}else if(now<=n&&st[now]==-1&&(k[1].empty()||a[now]<k[1].top())){
			k[1].push(a[now++]);
			q.push(2);
		}else if(!k[1].empty()&&k[1].top()==c){
			k[1].pop();c++;
			q.push(3);
		}else{printf("0");return 0;}
	}
	putchar(q.front()+'a');q.pop();
	while(!q.empty()){printf(" %c",q.front()+'a');q.pop();}
	return 0;
}

// <twostack.cpp> - 02/29/16 22:12:20

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=1002;

stack <int> k[2];

queue <int> q;

int a[MAXN],c[MAXN],st[MAXN];

vector <int> b[MAXN];

void color(int x){

for(int i=0;i<b[x].size();i++){

int next=b[x][i];

if(st[next])continue;

st[next]=-st[x];

color(next);

}

int main(){

freopen("twostack.in","r",stdin);

freopen("twostack.out","w",stdout);

int n=getint();

for(int i=1;i<=n;i++)a[i]=getint();

c[n]=a[n];

for(int i=n-1;i;i--)c[i]=min(c[i+1],a[i]);

for(int i=1;i<n-1;i++)

for(int j=i+1;j<n;j++)

if(a[i]<a[j]&&c[j+1]<a[i]){b[i].push_back(j);b[j].push_back(i);}

for(int i=1;i<=n;i++)if(!st[i]){st[i]=1;color(i);}

int now=1,c=1;

while(q.size()!=n<<1){

if(now<=n&&st[now]==1&&(k[0].empty()||a[now]<k[0].top())){

k[0].push(a[now++]);

q.push(0);

}else if(!k[0].empty()&&k[0].top()==c){

k[0].pop();c++;

q.push(1);

}else if(now<=n&&st[now]==-1&&(k[1].empty()||a[now]<k[1].top())){

k[1].push(a[now++]);

q.push(2);

}else if(!k[1].empty()&&k[1].top()==c){

k[1].pop();c++;

q.push(3);

}else{printf("0");return 0;}

}

putchar(q.front()+'a');q.pop();

while(!q.empty()){printf(" %c",q.front()+'a');q.pop();}

return 0;

}