【bzoj4278】[ONTAK2015]Tasowanie 贪心+后缀数组

题目描述

给定两个数字串A和B，通过将A和B进行二路归并得到一个新的数字串T，请找到字典序最小的T。

输入

第一行包含一个正整数n(1<=n<=200000)，表示A串的长度。

第二行包含n个正整数，其中第i个数表示A[i](1<=A[i]<=1000)。

第三行包含一个正整数m(1<=m<=200000)，表示B串的长度。

第四行包含m个正整数，其中第i个数表示B[i](1<=B[i]<=1000)。

输出

输出一行，包含n+m个正整数，即字典序最小的T串。

样例输入

6
1 2 3 1 2 4
7
1 2 2 1 3 4 3

样例输出

1 1 2 2 1 2 3 1 2 3 4 3 4

题解

贪心+后缀数组

贪心法则：选择字典序小的串。

那么我们就可以将两个串放到一起，利用后缀数组求排名，减少时间。

需要注意的是两个串之间需要加一个最大数，因为如果第一个串全部用完，rank应该为最大。

#include <cstdio>

#define N 400005

int ws[N] , wv[N] , wa[N] , wb[N] , sa[N] , r[N] , rank[N] , m = 1003 , n , a[N];

void da()

{

    int i , j , p , *x = wa , *y = wb , *t;

    for(i = 0 ; i < m ; i ++ ) ws[i] = 0;

    for(i = 0 ; i < n ; i ++ ) ws[x[i] = r[i]] ++ ;

    for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1];

    for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[i]]] = i;

    for(p = j = 1 ; p < n ; j <<= 1 , m = p)

    {

        for(p = 0 , i = n - j ; i < n ; i ++ ) y[p ++ ] = i;

        for(i = 0 ; i < n ; i ++ ) if(sa[i] - j >= 0) y[p ++ ] = sa[i] - j;

        for(i = 0 ; i < n ; i ++ ) wv[i] = x[y[i]];

        for(i = 0 ; i < m ; i ++ ) ws[i] = 0;

        for(i = 0 ; i < n ; i ++ ) ws[wv[i]] ++ ;

        for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1];

        for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[wv[i]]] = y[i];

        for(t = x , x = y , y = t , x[sa[0]] = 0 , p = i = 1 ; i < n ; i ++ )

        {

            if(y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j])

                x[sa[i]] = p - 1;

            else

                x[sa[i]] = p ++ ;

        }

    }

    for(i = 1 ; i < n ; i ++ )

        rank[sa[i]] = i;

}

int main()

{

    int n1 , n2 , i , p1 , p2;

    scanf("%d" , &n1);

    for(i = 0 ; i < n1 ; i ++ )

    {

        scanf("%d" , &a[i]);

        r[i] = a[i];

    }

    scanf("%d" , &n2);

    for(i = n1 + 1 ; i < n1 + n2 + 1 ; i ++ )

    {

        scanf("%d" , &a[i]);

        r[i] = a[i];

    }

    r[n1] = 1001;

    r[n1 + n2 + 1] = 0;

    n = n1 + n2 + 2;

    da();

    p1 = 0;

    p2 = n1 + 1;

    while(p1 < n1 || p2 < n1 + n2 + 1)

    {

        if(p2 < n1 + n2 + 1 && rank[p2] < rank[p1])

            printf("%d " , a[p2 ++ ]);

        else

            printf("%d " , a[p1 ++ ]);

    }

    printf("\n");

    return 0;

}

巴特西

【bzoj4278】[ONTAK2015]Tasowanie 贪心+后缀数组

最新文章

热门文章