题目描述
FJ打算带他的N(1 <= N <= 30,000)头奶牛去参加一年一度的“全美农场主大奖赛”。在这场比赛中，每个参赛者都必须让他的奶牛排成一列，然后领她们从裁判席前依次走过。 今年，竞赛委员会在接受队伍报名时，采用了一种新的登记规则：他们把所有队伍中奶牛名字的首字母取出，按它们对应奶牛在队伍中的次序排成一列（比如说，如果FJ带去的奶牛依次为Bessie、Sylvia、Dora，登记人员就把这支队伍登记为BSD）。登记结束后，组委会将所有队伍的登记名称按字典序升序排列，就得到了他们的出场顺序。 FJ最近有一大堆事情，因此他不打算在这个比赛上浪费过多的时间，也就是说，他想尽可能早地出场。于是，他打算把奶牛们预先设计好的队型重新调整一下。 FJ的调整方法是这样的：每次，他在原来队列的首端或是尾端牵出一头奶牛，把她安排到新队列的尾部，然后对剩余的奶牛队列重复以上的操作，直到所有奶牛都被插到了新的队列里。这样得到的队列，就是FJ拉去登记的最终的奶牛队列。 接下来的事情就交给你了：对于给定的奶牛们的初始位置，计算出按照FJ的调整规则所可能得到的字典序最小的队列。
输入
* 第1行: 一个整数：N
* 第2..N+1行: 第i+1行仅有1个‘A‘..‘Z‘中的字母，表示队列中从前往后数第i 头奶牛名字的首字母
输出
* 第1..??行: 输出FJ所能得到的字典序最小的队列。每行（除了最后一行）输出恰好80个‘A‘..‘Z‘中的字母，表示新队列中每头奶牛姓名的首字母
样例输入
6
A
C
D
B
C
B
样例输出
ABCBCD
题解
贪心+后缀数组
由题意易知贪心法则：优先取字典序小的一端并删除，直至结束。
然而每次都比较前后的字典序大小会TLE。
于是想到后缀数组。
可以先把原串翻转并放到其后面，然后求出rank。
这样，每次比较前后的字典序时，直接比较前面字符在前半部分的rank和后面字符在后半部分的rank即可。
注意题目要求：“每行（除了最后一行）输出恰好80个‘A‘..‘Z‘中的字母”。
1 #include <cstdio> 2 #define N 60002 3 int ws[N] , wv[N] , wa[N] , wb[N] , sa[N] , r[N] , rank[N] , n , m = 28; 4 char str[3] , s[N]; 5 void da() 6 { 7 int i , j , p , *x = wa , *y = wb , *t; 8 for(i = 0 ; i < m ; i ++ ) ws[i] = 0; 9 for(i = 0 ; i < n ; i ++ ) ws[x[i] = r[i]] ++ ; 10 for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1]; 11 for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[i]]] = i; 12 for(j = p = 1 ; p < n ; j <<= 1 , m = p) 13 { 14 for(p = 0 , i = n - j ; i < n ; i ++ ) y[p ++ ] = i; 15 for(i = 0 ; i < n ; i ++ ) if(sa[i] - j >= 0) y[p ++ ] = sa[i] - j; 16 for(i = 0 ; i < n ; i ++ ) wv[i] = x[y[i]]; 17 for(i = 0 ; i < m ; i ++ ) ws[i] = 0; 18 for(i = 0 ; i < n ; i ++ ) ws[wv[i]] ++ ; 19 for(i = 1 ; i < m ; i ++ ) ws[i] += ws[i - 1]; 20 for(i = n - 1 ; i >= 0 ; i -- ) sa[--ws[wv[i]]] = y[i]; 21 for(t = x , x = y , y = t , x[sa[0]] = 0 , p = i = 1 ; i < n ; i ++ ) 22 { 23 if(y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) 24 x[sa[i]] = p - 1; 25 else 26 x[sa[i]] = p ++ ; 27 } 28 } 29 for(i = 1 ; i < n ; i ++ ) 30 rank[sa[i]] = i; 31 } 32 int main() 33 { 34 int i , l , le , ri; 35 scanf("%d" , &l); 36 for(i = 0 ; i < l ; i ++ ) 37 { 38 scanf("%s" , str); 39 s[i] = s[2 * l - i - 1] = str[0]; 40 r[i] = r[2 * l - i - 1] = str[0] - ‘A‘ + 1; 41 } 42 r[2 * l] = 0; 43 n = 2 * l + 1; 44 da(); 45 le = 0; 46 ri = l - 1; 47 for(i = 1 ; i <= l ; i ++ ) 48 { 49 if(rank[le] < rank[2 * l - ri - 1]) printf("%c" , s[le ++ ]); 50 else printf("%c" , s[ri -- ]); 51 if(i % 80 == 0) printf("\n"); 52 } 53 return 0; 54 }
原文：http://www.cnblogs.com/GXZlegend/p/6269851.html