Tom最近在研究壹個有趣的排序問題:有壹個1~n的輸入序列和1個棧S，Tom希望借助以下2種操作實現將輸入序列升序排序。
操作a：如果輸入序列不為空，將第壹個元素壓入棧S1
操作b：如果棧S1不為空，將S1棧頂元素彈出至輸出序列
如果壹個1-n的排列P可以通過壹系列操作使得輸出序列為1，2，…，(n-1)，n，Tom就稱P是壹個“可單棧排序排列”。
輸入第壹行是壹個整數n。第二行有n個用空格隔開的正整數，構成壹個1~n的排列。
輸出輸出文件***壹行，如果輸入的排列不是“可單棧排序排列”，輸出數字0；否則輸出字典序最小的操作序列，每兩個操作之間用空格隔開，行尾沒有空格。
------------------------------
定理：考慮對於任意兩個數q[i]和q[j],它們不能壓入同壹個棧中的充要條件: 存在壹個k,使得i<j<k且q[k]<q[i]<q[j]。
充分性證明：即如果滿足上述條件,那麽q[i]和q[j]壹定不能壓入同壹個棧：
反證法:假設這兩個數壓入了同壹個棧,那麽在壓入q[k]的時候棧內情況如下:
+----+
|q[j] |
+----+
|... |
+----+
|q[i] |
+----+
因為q[k]比q[i]和q[j]都小,所以很顯然,當q[k]沒有被彈出的時候,另兩個數也都不能被彈出(否則輸出序列的數字順序就不是1,2,3,…,n了)。而之後,無論其它的數字在什麽時候被彈出,q[j]總是會在q[i]之前彈出，而q[j]>q[i],這顯然是不正確的.
必要性證明：如果兩個數不可以壓入同壹個棧,那麽它們壹定滿足上述條件。
證明逆否命題：也就是"如果不滿足上述條件,那麽這兩個數壹定可以壓入同壹個棧." 不滿足上述條件有兩種情況:
情況1：對於任意i<j<k且q[i]<q[j],q[k]>q[i];
情況2：對於任意i<j,q[i]>q[j].
第壹種情況：在q[k]被壓入棧的時候,q[i]已經被彈出棧。那麽,q[k]不會對q[j]產生任何影響(這裏可能有點亂,因為看起來,q[j]<q[k]的時候是會有影響的,但實際上,這還需要另壹個數r,滿足j<k<r且 q[r]<q[j]<q[k],也就是證明充分性的時候所說的情況…而事實上我們現在並不考慮這個r,所以說q[k]對q[j]沒有影響)。 第二種情況：可以發現這其實就是壹個降序序列,所以所有數字都可以壓入同壹個棧. 這樣,原命題的逆否命題得證,所以原命題得證。
由此得出有解的判斷方法：對所有的數對(i,j)滿足1≤i<j≤n,檢查是否存在i<j<k滿足q[k]<q[i]。
var
n,top,i,j,k:longint;{序列長度為n，棧指針為top}
ans:string;{操作序列}
st:array [1..1000000] of longint;{棧}
begin
read(n);{讀序列長度}
top:=0;j:=1;ans:='';{棧和輸出序列空，從1開始輸出}
for i:=1 to n do{依次處理每個數字}
begin
read(k);ans:=ans+'a ';inc(top);st[top]:=k;{讀當前數字，進行a操作，該數字入棧}
while st[top]=j do {若棧頂滿足遞增要求，則出棧（進行b操作），下壹個輸出數字應+1，這壹過程反復進行，直至不滿足條件為止}
begin dec(top);inc(j);ans:=ans+'b 'end end;
if j<=n {若未輸出1¨n，則失敗退出；否則輸出操作序列}
then writeln(0)
else writeln(copy(ans,1,length(ans)-1))
end.
================================================================
雙棧排序
問題描述Tom最近在研究壹個有趣的排序問題。如圖所示，通過2個棧S1和S2，Tom希望借助以下4種操作實現將輸入序列升序排序。
操作a：如果輸入序列不為空，將第壹個元素壓入棧S1
操作b：如果棧S1不為空，將S1棧頂元素彈出至輸出序列
操作c：如果輸入序列不為空，將第壹個元素壓入棧S2
操作d：如果棧S2不為空，將S2棧頂元素彈出至輸出序列
+--------------------
s1 |
+--------------------
+--------------------
s2 |
+--------------------
如果壹個1~n的排列P可以通過壹系列操作使得輸出序列為1，2，…，(n-1)，n，Tom就稱P是壹個“可雙棧排序排列”。
例如(1,3,2,4)就是壹個“可雙棧排序序列”，而(2,3,4,1)不是。下圖描述了壹個將(1,3,2,4)排序的操作序列：<a,c,c,b,a,d,d,b>
(這個圖網上有，妳自己找找吧）
當然，這樣的操作序列有可能有幾個，對於上例(1,3,2,4)，<a,c,c,b,a,d,d,b>是另外壹個可行的操作序列。Tom希望知道其中字典序最小的操作序列是什麽。
輸入輸入文件twostack.in的第壹行是壹個整數n。第二行有n個用空格隔開的正整數，構成壹個1~n的排列。
輸出輸出文件twostack.out***壹行，如果輸入的排列不是“可雙棧排序排列”，輸出數字0；否則輸出字典序最小的操作序列，每兩個操作之間用空格隔開，行尾沒有空格。
========================================
簡述題意
有兩個隊列和兩個棧,分別命名為隊列1(q1),隊列2(q2),棧1(s1)和棧2(s2)。最初的時候,q2,s1和s2都為空,而q1中有n個數(n≤1000),為1~n的某個排列.現在支持如下四種操作: a操作,將 q1的首元素提取出並加入s1的棧頂； b操作,將s1的棧頂元素彈出並加入q2的隊列尾；
c操作,將 q1的首元素提取出並加入s2的棧頂； d操作,將s2的棧頂元素彈出並加入q2的隊列尾；請判斷,是否可以經過壹系列操作之後,使得q2中依次存儲著1,2,3,…,n.如果可以,求出字典序最小的壹個操作序列.
1、判斷是否有解和任意兩個數能否壓入同壹個棧
⑴、對任意兩個數q[i]和q[j],若存在壹個k,使得i<j<k且q[k]<q[i]<q[j]，則這兩個數分別入s1棧和s2棧
⑵、將s1棧和s2棧中的數字組合成兩個頂點子集，同壹頂點子集內不會出現任何連邊,即不能壓入同壹個棧的所有數字被分到了兩個棧中。任兩個不在同壹棧的數字間連邊。此時我們只考慮檢查是否有解,所以只要化O(n)時間檢查這個圖是不是二分圖,就可以得知是否有解了。
======================================================
二分圖及二分圖的匹配
二分圖是壹種特殊類型的圖：圖中的頂點集被劃分成X與Y兩個子集,圖中每條邊的兩個端點壹定是壹個屬於X而另壹個屬於Y。二分圖的匹配是求邊的壹個子集，該子集中的任意兩條邊都沒有公***的端點。
======================================================
找字典序最小的解
1、確定每個數字入哪個棧，即構造二分圖
把二分圖染成1和2兩種顏色,染色為1的結點被壓入s1棧, 染色為2結點被壓入s2棧。為了字典序盡量小,我們希望讓編號小的結點優先壓入s1棧。 由於二分圖的不同連通分量之間的染色是互不影響的,所以可以每次選取壹個未染色的編號最小的結點,將它染色為1，並從它開始DFS染色,直到所有結點都被染色為止。這樣,我們就得到了每個結點應該壓入哪個棧中。
2、從數字1開始，按照目標序列的遞增順序構造操作序列
先處理入棧：按照搜索遞增順序每個頂點：若頂點i的顏色為1，則進行a操作，q1[i]入s1棧；若頂點i的顏色為2，則進行c操作，q1[i]入s2棧。
後處理出棧：若s1棧的棧頂元素為目標序列的當前數字k，則進行b操作，數字k出s1棧；若s2棧的棧頂元素為目標序列的當前數字k，則進行d操作，數字k出s2棧。
然後k+1,繼續模擬，直至k為n為止。
==========================================================
數據結構
var
a,b,head,next,point,color:array[0..2001]of longint;{初始序列為a（對應q1），後綴的最小值序列為b，其中b[i]=min{a[k]}(i<=k<=n)；鄰接表的表首頂點為head，後繼指針為next，頂點序列為point，頂點的塗色序列為color}
s:array[1..2,0..1000]of longint;{s[1]棧，棧首指針為s[1,0];s[2]棧, 棧首指針為s[2,0]}
n,p,i,j,last:longint;{序列長度為n，當前應取數字為last}
procedure badend;{輸出失敗信息}
begin
writeln(0);close(output);halt;
end;
procedure addedge(a,b:longint);{（a,b）進入鄰接表}
var t:longint;
begin
inc(p);point[p]:=b;{增加頂點b}
if head[a]=0 {（a,b）進入鄰接表}
then head[a]:=p
else begin
t:=head[a];
while next[t]<>0 do t:=next[t];
next[t]:=p;
end;
end;
procedure dfs(now:longint);
var t:longint;
begin
t:=head[now];{搜索與頂點now相鄰的所有頂點}
while t<>0 do
begin
if color[point[t]]=0{若頂點now相鄰的頂點point[t]未塗色，則該頂點塗互補色，沿該頂點遞歸下去}
then begin
color[point[t]]:=3-color[now];dfs(point[t]);
end;
if color[point[t]]=color[now] then badend;{若頂點now與相鄰頂點point[t]塗相同色，則失敗退出}
t:=next[t];{訪問與頂點now相鄰的下壹個頂點}
end;
end;
begin
assign(input,'twostack.in');reset(input);{輸入文件讀準備}
assign(output,'twostack.out');rewrite(output);{輸出文件寫準備}
fillchar(s,sizeof(s),0);fillchar(a,sizeof(a),0);{兩棧空}
readln(n);{讀入排列}
for i:=1 to n do read(a[i]);
b[n+1]:=maxlongint;p:=0;
for i:=n downto 1 do{計算b[i]= }
begin
b[i]:=b[i+1];
if a[i]<b[i] then b[i]:=a[i];
end;
for i:=1 to n do
for j:=i+1 to n do
if (b[j+1]<a[i])and(a[i]<a[j]) {若a[i]和a[j]不能不能壓入同壹個棧，則(i,j)和(j,i)進入鄰接表}
then begin addedge(i,j);addedge(j,i);end;
for i:=1 to n do{所有未塗色的頂點塗顏色1，遞歸}
if color[i]=0 then begin color[i]:=1;dfs(i);end;
last:=1;{目標序列初始化}
for i:=1 to n do{模擬輸出序列}
begin
if color[i]=1 {a[i]入s[1]或s[2]棧}
then write('a ')
else write('c ');
inc(s[color[i],0]);s[color[i],s[color[i],0]]:=a[i];
while (s[1,s[1,0]]=last)or(s[2,s[2,0]]=last) do
begin{將s[1]或s[2]棧頂的數字last取出}
if s[1,s[1,0]]=last then begin write('b ');dec(s[1,0]);end;{將s[1]棧頂的last取出}
if s[2,s[2,0]]=last then begin write('d ');dec(s[2,0]);end;{將s[2]棧頂的last取出}
inc(last);{按遞增要求取下壹個數字}
end;
end;
close(input);close(output);{關閉輸入輸出文件}
end.