题目描述
输入
输出
样例输入
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应该为最大。
1 #include <cstdio> 2 #define N 400005 3 int ws[N] , wv[N] , wa[N] , wb[N] , sa[N] , r[N] , rank[N] , m = 1003 , n , a[N]; 4 void da() 5 { 6 int i , j , p , *x = wa , *y = wb , *t; 7 for(i = 0 ; i < m ; i ++ ) ws[i] = 0; 8 for(i = 0 ; i < n ; i ++ ) ws[x[i] = r[i]] ++ ; 9 for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1]; 10 for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[i]]] = i; 11 for(p = j = 1 ; p < n ; j <<= 1 , m = p) 12 { 13 for(p = 0 , i = n - j ; i < n ; i ++ ) y[p ++ ] = i; 14 for(i = 0 ; i < n ; i ++ ) if(sa[i] - j >= 0) y[p ++ ] = sa[i] - j; 15 for(i = 0 ; i < n ; i ++ ) wv[i] = x[y[i]]; 16 for(i = 0 ; i < m ; i ++ ) ws[i] = 0; 17 for(i = 0 ; i < n ; i ++ ) ws[wv[i]] ++ ; 18 for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1]; 19 for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[wv[i]]] = y[i]; 20 for(t = x , x = y , y = t , x[sa[0]] = 0 , p = i = 1 ; i < n ; i ++ ) 21 { 22 if(y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) 23 x[sa[i]] = p - 1; 24 else 25 x[sa[i]] = p ++ ; 26 } 27 } 28 for(i = 1 ; i < n ; i ++ ) 29 rank[sa[i]] = i; 30 } 31 int main() 32 { 33 int n1 , n2 , i , p1 , p2; 34 scanf("%d" , &n1); 35 for(i = 0 ; i < n1 ; i ++ ) 36 { 37 scanf("%d" , &a[i]); 38 r[i] = a[i]; 39 } 40 scanf("%d" , &n2); 41 for(i = n1 + 1 ; i < n1 + n2 + 1 ; i ++ ) 42 { 43 scanf("%d" , &a[i]); 44 r[i] = a[i]; 45 } 46 r[n1] = 1001; 47 r[n1 + n2 + 1] = 0; 48 n = n1 + n2 + 2; 49 da(); 50 p1 = 0; 51 p2 = n1 + 1; 52 while(p1 < n1 || p2 < n1 + n2 + 1) 53 { 54 if(p2 < n1 + n2 + 1 && rank[p2] < rank[p1]) 55 printf("%d " , a[p2 ++ ]); 56 else 57 printf("%d " , a[p1 ++ ]); 58 } 59 printf("\n"); 60 return 0; 61 }
【bzoj4278】[ONTAK2015]Tasowanie
原文：http://www.cnblogs.com/GXZlegend/p/6272282.html