BZOJ 1692: [Usaco2007 Dec]隊列變換( 貪心 )

數據 n <= 30000 , 然后 O( n2 ) 的貪心也過了..... USACO 數據是有多弱啊 = =

( ps : BZOJ 1640 和此題一模一樣 , 雙倍經驗 )?

--------------------------------------------------------------------------------------

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#define rep( i , n ) for( int i = 0 ; ?i < n ; ++i )

#define clr( x , c ) memset( x , c , sizeof( x ) )

using namespace std;

const int maxn = 30000 + 5;

char seq[ maxn ];

char ans[ maxn ];

int n;

int cur = 0;

void Read() {

cin >> n;

rep( i , n ) {

char c = getchar();

while( ! isupper( c ) )

? ?c = getchar();

seq[ i ] = c;

}

}

bool cmp( int l , int r ) {

while( l < r && seq[ l ] == seq[ r ] )?

? ?l++ , r--;

return seq[ l ] < seq[ r ];

}

void print() {

rep( i , cur ) {

putchar( ans[ i ] );

if( ! ( ( i + 1 ) % 80 ) )

? ?printf( "\n" );

}

}

int main() {

Read();

int L = 0 , R = n - 1;

while( n-- )

ans[ cur++ ] = cmp( L , R ) ? seq[ L++ ] : seq[ R-- ];

print();

return 0;

}

?

--------------------------------------------------------------------------------------?

?

1692: [Usaco2007 Dec]隊列變換

Time Limit:?5 Sec??Memory Limit:?64 MB
Submit:?812??Solved:?330
[Submit][Status][Discuss]

Description

FJ打算帶他的N(1 <= N <= 30,000)頭奶牛去參加一年一度的“全美農場主大獎賽”。在這場比賽中，每個參賽者都必須讓他的奶牛排成一列，然后領她們從裁判席前依次走過。 今年，競賽委員會在接受隊伍報名時，采用了一種新的登記規則：他們把所有隊伍中奶牛名字的首字母取出，按它們對應奶牛在隊伍中的次序排成一列（比如說，如果FJ帶去的奶牛依次為Bessie、Sylvia、Dora，登記人員就把這支隊伍登記為BSD）。登記結束后，組委會將所有隊伍的登記名稱按字典序升序排列，就得到了他們的出場順序。 FJ最近有一大堆事情，因此他不打算在這個比賽上浪費過多的時間，也就是說，他想盡可能早地出場。于是，他打算把奶牛們預先設計好的隊型重新調整一下。 FJ的調整方法是這樣的：每次，他在原來隊列的首端或是尾端牽出一頭奶牛，把她安排到新隊列的尾部，然后對剩余的奶牛隊列重復以上的操作，直到所有奶牛都被插到了新的隊列里。這樣得到的隊列，就是FJ拉去登記的最終的奶牛隊列。 接下來的事情就交給你了：對于給定的奶牛們的初始位置，計算出按照FJ的調整規則所可能得到的字典序最小的隊列。

Input

* 第1行: 一個整數：N

* 第2..N+1行: 第i+1行僅有1個'A'..'Z'中的字母，表示隊列中從前往后數第i 頭奶牛名字的首字母

Output

* 第1..??行: 輸出FJ所能得到的字典序最小的隊列。每行（除了最后一行）輸 出恰好80個'A'..'Z'中的字母，表示新隊列中每頭奶牛姓名的首 字母

Sample Input

6
A
C
D
B
C
B

輸入說明:

FJ有6頭順次排好隊的奶牛：ACDBCB

Sample Output

ABCBCD

輸出說明:

操作數 原隊列 新隊列
#1 ACDBCB
#2 CDBCB A
#3 CDBC AB
#4 CDB ABC
#5 CD ABCB
#6 D ABCBC
#7 ABCBCD

HINT

Source

Gold

?