考慮任意兩個數q1[i]和q1[j]不能被推入同壹個堆棧的充要條件是什麽(註意，不需要使它們同時存在於同壹個堆棧中，只需要推入同壹個堆棧即可)。實際上，這個條件P是:有壹個k，使I
首先我們證明充分性，即如果滿足條件p，那麽這兩個數壹定不能壓入同壹個棧。顯然，這個結論可以用歸謬法來證明。
假設這兩個數被壓入同壹個堆棧，壓入q1[k]時堆棧中的情況如下:
…q1[i]…q1[j]…
因為q1[k]比q1[i]和q1[j]小，顯然，當q1[k]沒有被彈出時，其他兩個數也不能被彈出(否則q2中的數值順序不是1，2，2)。
之後不管什麽時候彈出其他數字，q1[j]總是會在q1[i]之前彈出。和q 1[j]& gt；Q1[i]，明顯不正確。
接下來，證明必要性。即如果兩個數不能被壓入同壹個堆棧，那麽它們必須滿足條件p，這裏我們將證明它的否定命題，即“如果不滿足條件p，那麽這兩個數可以被壓入同壹個堆棧。”
當條件p不滿足時有兩種情況:壹種是對於任意I
第壹種情況，很明顯，當q1[k]被壓入堆棧時，q1[i]已經被彈出堆棧。那麽，q1[k]對q1[j]不會有任何影響(這裏可能有點亂，因為好像當Q1 [j]時，當q1[k]時，會有影響，但實際上需要另壹個數r來滿足j
在第二種情況下，我們可以發現這實際上是壹個降序序列，所以所有的數字都可以被壓入同壹個堆棧中。
這樣就證明了原命題的否定命題，所以證明了原命題。
至此，條件P為q1[i]和q1[j]不能推入同壹棧的充要條件也得到證明。
這樣我們滿足1 < = I & lt；j & lt=n，檢查是否有I
壹個二分圖的兩個部分被看作兩個棧，因為二分圖的同壹個部分不會有邊，這意味著所有不能壓入同壹個棧的節點都被分成兩個棧。
這個時候我們只考慮檢查是否有解，所以只要o(n)檢查圖是否是二分的，就可以知道是否有解。
然後處理最小字典序問題。事實上，顯而易見的是，在對二部圖進行著色後，數目較小的運算優先於相應的運算，這樣可以使字典序盡可能小。
這裏我想提壹下二部圖的壹個性質:二部圖中不同連通分量的著色互不影響。因此，為了滿足最小字典序的問題，我們可以選擇編號最小的未著色節點對1進行染色，並對其連通分量進行染色。染色後模擬輸出順序就可以了。
(以下代碼部分僅供學習)
定義變量
n，I，j，st1，st2，next_num，min，t:longint；
a，顏色，s1，s2:數組[0..longint的1500]；
映射:數組[1..1500,1..布爾型的1500]；
vis:array[1..布爾型的1500]；
答案:數組[1..3000]的char
程序打印；
開始
writeln(0)；
停止；
結束；
過程dfs(x，now color:longint)；
定義變量
我:渴望；
開始
vis[x]:= true；
color[x]:= now color；
對於i:=1到n do
如果映射[x，i]那麽
開始
如果不是，那麽
dfs(i，3-nowcolor)
其他
if color[I]& lt；& gt3-立即著色然後打印；
結束；
結束；
開始
readln(n)；
對於i:=1到n do
讀(a[I])；
readln
min:= maxlongint；
for i:=n downto 1 do
開始
對於j:=1至i-1 do
if(a[j]& lt；a[i])和(min & lta[j]然後
開始
map[a[i]，a[j]]:= true；
map[a[j]，a[I]]:= true；
結束；
如果a[I]& lt；min then min:= a[I]；
結束；
fillchar(vis，sizeof(vis)，0)；
對於i:=1到n do
如果不是vis[a[i]]那麽dfs(a[i]，1)；
I:= 1；
next _ num:= 1；
t:= a[I]；
ST 1:= 0；
st2:= 0；
j:= 0；
while(我& lt=n)或(next _ num & lt做
開始
如果(我& lt= n)and(color[t]= 1)and((ST 1 = 0)or(t & lt；s1[st1])，然後
開始
Inc(j)；
ans[j]:= ' a '；
Inc(ST 1)；
s 1[ST 1]:= t；
inc(壹)；
如果我& lt=n那麽t:=a[i]否則t:= 0；
繼續；
結束；
if(ST 1 & gt；0)和(s1[st1]=next_num)則
開始
Inc(j)；
ans[j]:= ' b '；
dec(ST 1)；
Inc(next _ num)；
繼續；
結束；
如果(我& lt= n)and(color[t]= 2)and((st2 = 0)or(t & lt；s2[st2])，然後
開始
Inc(j)；
ans[j]:= ' c '；
Inc(st2)；
S2[st2]:= t；
inc(壹)；
如果我& lt=n那麽t:=a[i]否則t:= 0；
繼續；
結束；
如果(st2 & gt0)和(s2[st2]=next_num)則
開始
Inc(j)；
ans[j]:= ' d '；
十二月(st2)；
Inc(next _ num)；
繼續；
結束；
結束；
對於i:=1到j-1 do
寫(ans[i]，' ')；
writeln(ans[j])；
結束。