NOIP2008 双栈排序

link

Orz zjp_shadow.

考虑单栈的情况, 如果i<j<ki<j<kak<ai<aja_k<a_i<a_j,则无法排序,原因是在aka_k进栈之前,aja_j进栈时,aia_i还不能弹,当aka_k出栈后,aia_i显然不可能在aja_j前出栈。

现在增加了一个栈,所以这种情况还是有办法解决的:把ai,aja_i,a_j放进不同的栈就可以了。

也就是说,会出现一些两个数ai,aja_i,a_j不能放进同一个栈的限制,此时连边i,ji,j

如果得到的是个二分图,就可以把一边放入一个栈从而满足条件,否则就不行。

然后按照编号从小到大黑白染色(优先使编号小的进栈1)

接着依次对每个数考虑:首先把它压到该压到的栈,如果它是下一个要输出的数,那么就开始弹出尽量多的数。最后按顺序输出每个栈里的数。

这样看似正确,实则有一些问题。

实际上为了输出结果,我们只需要两个栈都是自顶到底单调递增的就可以了。

在开始弹出之前,如果这个数压在栈2,并且之后几个现在可以压入(显然是栈1的),那就先压再弹(压1(a)<弹2(d))

这样就能最优了……吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/*
Author: CNYALI_LK
LANG: C++
PROG: 1155.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline void read (int &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// print a signed integer
inline void write (int x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int a[1005],mn[1005];
int col[1005];
vector<int> to[1005];
void dfs(int x,int c){
if(~col[x]){if(col[x]!=c){write("0\n");exit(0);}return;}
col[x]=c;
for(int i=0,t=to[x].size();i<t;++i)dfs(to[x][i],c^1);
}
int s[2][1005],top[2],pos=1;
void push(int x,int y){
s[x][++top[x]]=y;
write(char('a'+2*x),' ');
}
int pop(int x){
if(s[x][top[x]]==pos){
write(char('b'+2*x),' ');
--top[x];
++pos;
return 1;
}
return 0;
}
int main(){
#ifdef cnyali_lk
freopen("1155.in","r",stdin);
freopen("1155.out","w",stdout);
#endif
int n,x;
read(n);
for(int i=1;i<=n;++i){
read(a[i]);
}
mn[n+1]=inf;
for(int i=n;i;--i)mn[i]=min(mn[i+1],a[i]);
for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j)if(a[i]<a[j] && mn[j+1]<a[i]){to[i].push_back(j);to[j].push_back(i);}
for(int i=1;i<=n;++i)col[i]=-1;
for(int i=1;i<=n;++i)if(!~col[i])dfs(i,0);
col[n+1]=-1;
/* for(int i=1;i<=n;++i)write(col[i]);
return 0;*/
for(int i=1;i<=n;++i){
push(col[i],a[i]);
if(a[i]==pos){
if(col[i]==1)while(!col[i+1] && s[0][top[0]]>a[i+1]){++i;push(0,a[i]);}
pop(col[i]);
while(s[0][top[0]]==pos || s[1][top[1]]==pos)pop(0)||pop(1);
}
}
for(;pos<=n;){
while(pop(0));
while(pop(1));
}

return 0;
}
文章目录
|

博客使用Disqus作为评论系统