poj3581Sequence(后缀数组)

转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud

Sequence

Time Limit: 5000MS		Memory Limit: 65536K
Case Time Limit: 2000MS

Description

Given a sequence, {A₁, A₂, ..., A_n} which is guaranteed A₁> A₂, ..., A_n, you are to cut it into three sub-sequences and reverse them separately to form a new one which is the smallest possible sequence in alphabet order.

The alphabet order is defined as follows: for two sequence {A₁, A₂, ..., A_n} and {B₁, B₂, ..., B_n}, we say {A₁, A₂, ..., A_n} is smaller than {B₁, B₂, ..., B_n} if and only if there exists such i ( 1 ≤ i ≤ n) so that we have A_i < B_{i and}A_j = B_j for each j < i.

Input

The first line contains n. (n ≤ 200000)

The following n lines contain the sequence.

Output

output n lines which is the smallest possible sequence obtained.

Sample Input

Sample Output

Hint

{10, 1, 2, 3, 4} -> {10, 1 | 2 | 3, 4} -> {1, 10, 2, 4, 3}

题意：

给出n个数，把这个数列分为三段，再把三段反转后连接在一起成为一个新串，求字典序最小的新串。

思路：

由于第一个数保证比其他所有数要大，在取第一段时直接取反转后的字典序最小的后缀即可。利用后缀数组即可求得。

而后把剩下的一个字符串中分成两段，使得其字典序最小。首先我们会很容易的想到向第一段一样的方法，即取反转之后的字典序最小的后缀。

但对于这种方法，我们很容易就能找到一组反例，即10 1 2 2 3

按照上述的方法，我们会取得第一段为10 1，反转，变为1 10

而后剩下的字符串为2 2 3，对于此串，反转之后为3 2 2，字典序最小的为2.整个串则变为1 10 2 3 2

显然当我们取2 2的时候整个串的字典序才是最小的，为1 10 2 2 3。

对于一个长度为m的串s[1]……s[m]，设我们取将其分成s[1]……s[k]和s[k+1]……s[m]

将其反转之后则为s[k]……s[1]s[m]……s[k+1],我们可以发现，这个串正是s[m]……s[k+1]s[k]……s[1]s[m]……s[k+1]s[k]……s[1]的子串，并且我们可以通过找这个串的长度大于m字典序最小的后缀从而得到答案。

对于上例3 2 2，可变成3 2 2 3 2 2，长度大于m的字典序最小的后缀就是2 2 3 2 2。取其前一段即为所求的第二段。

另外，本题必须为单组输入，否则会WA，这点坑了我好久。。。。。

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 using namespace std;

 #define MAXN 400010

 int n,k;

 int sa[MAXN],rank[MAXN],a[MAXN],b[MAXN],c[MAXN],tmp[MAXN];

 bool cmp(int i,int j){

     if(rank[i]!=rank[j])return rank[i]<rank[j];

     else {

         int ri=i+k<=n?rank[i+k]:-1e8;

         int rj=j+k<=n?rank[j+k]:-1e8;

         return ri<rj;

     }

 }

 void build(int len,int *s){

     n=len;

     for(int i=;i<=n;i++)sa[i]=i,rank[i]=i<n?s[i]:-1e8;

     for(k=;k<=n;k<<=){

         sort(sa,sa+n+,cmp);

         tmp[sa[]]=;

         for(int i=;i<=n;i++){

             tmp[sa[i]]=tmp[sa[i-]]+(cmp(sa[i-],sa[i])?:);

         }

         for(int i=;i<=n;i++)rank[i]=tmp[i];

     }

 }

 int main()

 {

     int N;

     scanf("%d",&N);

     //while(scanf("%d",&N)!=EOF){

         for(int i=;i<N;i++)scanf("%d",a+i);

         for(int i=;i<N;i++)b[i]=a[N--i];

         build(N,b);

         int p1;

         for(int i=;i<=N;i++){

             p1=N-sa[i]-;

             if(p1>=&&p1+<=n)break;

         }

         int m=N-p1-;

         for(int i=;i<m;i++)c[i]=a[i+p1+];

         for(int i=;i<m;i++)b[i]=b[i+m]=c[m--i];

         build(*m,b);

         int p2;

         for(int i=;i<=*m;i++)

         {

             p2=m-sa[i]-;

             if(p2>=&&p2<=m-)break;

         }

         p2+=p1+;

         for(int i=p1;i>=;i--)printf("%d\n",a[i]);

         for(int i=p2;i>p1;i--)printf("%d\n",a[i]);

         for(int i=N-;i>p2;i--)printf("%d\n",a[i]);

     //}

     return ;

 }

代码君

巴特西

poj3581Sequence(后缀数组)

最新文章

热门文章