[ZJ d110][NOIP 2008 提高組][Bipartite Graph] 雙棧排序

原題連結
這題頗有趣的@@
首先想到的大概都是基於貪心的算法，我不免俗(?)的也覺得貪心蠻OK的，做完了傳上去當然是獲得WA。


那麼反例是像怎樣呢？

例如：
10
10 2 8 1 7 9 3 4 5 6

如果你的貪心策略跟我一樣，是按照優先順序嘗試每個操作，那對於這組數據應該會輸出0。

發生了什麼事呢？大概是像這樣的。(以括號右邊為堆疊的頂)

[10]
[]
--
[10,2]
[]
--
[10,2,1]
[]
--
[10,2]
[]
--
[10]
[]
--
[10]
[8]
--
[10,7]
[8]
--
到這邊9要進堆疊了，但是卻沒有合法操作！
觀察一下，問題是發生在最後一步：如果我們將7放入第二個堆疊，那麼就可以順利的輸出正解。

也就是問題在於：如果兩個堆疊都可以合法推入，且第一個堆疊的頂>第二個堆疊的頂，那麼選擇第一個推入雖可以獲得較小字典序，但是卻有可能遺失解答！因為說不定需要推入第二個堆疊以獲得更小的差距。( (10,7)和(8,7) 顯然是後者會比較優的)

所以貪心是要失效的，我們需要更「確定性」的方法來決定每個數字該推入哪個堆疊。
然後就出現了神奇的充要條件：

a[i]和a[j]不能放在同一個堆疊，當且僅當存在k使得i<j<k且a[k]<a[i]<a[j]

充分性相當顯然，但是必要性比較難證，這也是我一開始沒有主動想要依據此性質來設計算法的原因......證明略去，可以自行google。

有了這個性質之後，我們可以好好預處理所有不能在同個堆疊的數字(O(n^2))
問題有解當且僅當此圖是二分圖，即資訊互相不矛盾。

為了讓字典序最小，每次選擇位置最小還沒被染色的i，讓他進入第1個堆疊。再去二分染色與他有關的位置。

輸出解答就相當自然了，因為我們已經知道每個數字該進哪裡，所以不會推錯堆疊。那麼就可以O(n)出解。

#include<cstdio>
#include<cstdlib>
#include<stack>
#include<vector>
using namespace std;
const int maxn=1000+5;
const int INF=(1<<30);
vector<int> G[maxn];
int color[maxn],a[maxn];
bool bicolor(int now,int c)
{
    //printf("bicolor(%d,%d)\n",now,c);
    color[now]=c;
    for(int i=0;i<G[now].size();i++)
    {
        int to=G[now][i];
        if(color[to]==c) return 0;
        else if(color[to]==0 && !bicolor(to,3-c)) return 0;
    }
    return 1;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",a+i);
    for(int i=0;i<n;i++)
    {
        int Min=INF;
        for(int j=n-1;j>=i+1;j--)
        {
            if(Min<a[i] && a[i]<a[j]) {/*printf("i=%d j=%d Min=%d\n",i,j,Min);*/G[i].push_back(j);G[j].push_back(i);}
            Min=min(Min,a[j]);
        }
    }
    bool flag=1;
    for(int i=0;i<n;i++) if(!color[i] && !bicolor(i,1)) {flag=0;break;}
    if(!flag) printf("0\n");
    else
    {
        stack<int> S[2];
        vector<int> vec;
        int wanted=1;
        for(int i=0;wanted<=n;)
            for(int j=0;j<2;j++)
            {
                if(i<n && (S[j].empty() || S[j].top()>a[i]) && color[i]==j+1) {S[j].push(a[i++]);vec.push_back('a'+j*2);break;}
                else if(!S[j].empty() && S[j].top()==wanted) {S[j].pop();wanted++;vec.push_back('b'+j*2);break;}
            }
        for(int i=0;i<vec.size();i++) printf("%c%c",vec[i],i==vec.size()-1?'\n':' ');
    }
}