poj 1147 Binary codes BWT壓縮算法

題意：一個長度為N的01序列，會有N個不同的輪換（當然，字元相同，其中也可能會有相同的），将這N個不同輪換按字典序排

序，取排序後的每個輪換的最後一排，組成一個序列。題中給出壓縮後的序列，求原始序列，輸出的是字典序最小的那個序列。

思路：這題基于一個性質：在已經排序好的矩陣中，對于首位相同的兩行，經過左移一位的操作後，形成的新的兩行的先後次序不發

生改變。即:設i行在j行前面，i行左移一位變成p行，j左移一位後變成q行，p還是在q的前面。已知最後一列，那麼我們可以知道一行

有幾個零(cnt0個)幾個一(cnt1個)，那麼我們自然能得到第一列，前cnt0個為零，之後cnt1個為一。由上述性質，第一列第i個零所在的

p行一定是轉移到最後一列第i個零所在的q行，且q行的首位是是p行首位的後一位。那麼我們利用性質即可得到行轉移的數組next。

最後沿着next進行行轉移，依次輸出行的首位即為第一行，詳見代碼：

/*********************************************************
  file name: poj1147.cpp
  author : kereo
  create time:  2015年02月21日 星期六 18時08分02秒
*********************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=100+50;
const int MAXN=100000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=1000000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair<int, int>
#define mk(x,y) make_pair((x),(y))
int n,cnt0,cnt1;
int a[MAXN],num0[MAXN],num1[MAXN],next[MAXN];
int main(){
    while(~scanf("%d",&n)){
        cnt0=cnt1=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            if(a[i])
                cnt1++,num1[cnt1]=i;
            else 
                cnt0++,num0[cnt0]=i;
        }
        for(int i=1;i<=n;i++){
            if(i<=cnt0)
                next[i]=num0[i];
            else 
                next[i]=num1[i-cnt0];
        }
        int k=1,ans;
        for(int i=1;i<=n;i++){
            if(i == 1)
                printf("%d",ans=k<=cnt0 ? 0 : 1);
            else
                printf(" %d",ans=k<=cnt0 ? 0 : 1);
            k=next[k];
        }
        printf("\n");
    }
	return 0;
}