Poj 1147 Binary codes bwt压缩算法（很巧妙的一种算法）

题目连接：http://poj.org/problem?id=1147

题目描述：就是求解bwt压缩算法的逆过程。

一个长度为N的01序列，会有N个不同的轮换（当然，字符相同，其中也可能会有相同的），将这N个不同轮换按字典序排序，取排序后的每个轮换的最后一排，组成一个序列。题中给出压缩后的序列，求原始序列，输出的是字典序最小的那个序列

解法：整个解法还挺巧妙的，具体百度上也有解释，简单的根据体重给出的例子说一下：

0	0	0	1	1
0	0	1	1	0
0	1	1	0	0
1	0	0	0	1
1	1	0	0	0

给出的序列中0和1的个数肯定是和原始序列一样的，即由最后一列的数据10010可知原始序列中有2个0和3个1，所以将最后一列（10010）进行排序，即可得到第一列的数据（00011）。上述5*5数组中，将最后一列的数据移到第一列，得一下序列

 

1	0	0	0	1	①
0	0	0	1	1	②
0	0	1	1	0	③
1	1	0	0	0	④
0	1	1	0	0	⑤

（2）

而上述五个轮换中的第一列与第二列是可以知道的，如果要将上述五个轮换按字典序排序后变成（1），则需要进行相应转换，可知如果开头都是1或者都是0则先后顺序仍然不变，只需把①②③④⑤变成②③⑤①④即可，这个时候将（2）中的第二列（00011）与第一列（10010）同时变化，即可得到（1）中的第二列（00101），以此类推，现在（1）中的第一、二列都已经知道，按照同样的推演方式即可得到（1）中，即原始序列中的所有列的元素，即可得到原始序列。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define N 3010
using namespace std;
bool last[N], first[N], goal[N], temp[N];
int t[N];
int main(){
    int n, i, j, k, l;
    while(~scanf("%d",&n)){
        k=0;
        for(i=0;i<n;i++){
            scanf("%d",&last[i]);
            if(last[i]==0){
                first[k]=last[i];
                t[i] = k;
                k++;
            }
        }
        for(i=0;i<n;i++){
            if(last[i]==1){
                first[k]=last[i];
                t[i]=k;
                k++;
            }
        }
        goal[0]=first[0];
        for(j=1;j<n;j++){
            if(j%2){
                for(i=0;i<n;i++){
                    temp[t[i]]=first[i];
                }
                goal[j] = temp[0];
            }
            else{
                for(i=0;i<n;i++){
                    first[t[i]]=temp[i];
                }
                goal[j] = first[0];
            }
        }
        for(i=0;i<n-1;i++){
            printf("%d ",goal[i]);
        }
        printf("%d\n",goal[i]);
    }
    return 0;
}