OpenJ_Bailian3377

Best Cow Line, Gold

Time Limit:10000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

Submit Status Practice OpenJ_Bailian 3377

Description

FJ is about to take his N (1 <= N <= 30,000) cows to the annual "Farmer of the Year" competition. In this contest every farmer arranges his cows in a line and herds them past the judges.

The contest organizers adopted a new registration scheme this year: simply register the initial letter of every cow in the order they will appear (e.g., If FJ takes Bessie, Sylvia, and Dora in that order, he just registers BSD). After the registration phase ends, every group is judged in increasing lexicographic order (i.e., alphabetical order) according to the string of the initials of the cows' names.

FJ is very busy this year and has to hurry back to his farm, so he wants to be judged as early as possible. He decides to rearrange his cows, who have already lined up, before registering them.

FJ marks a location for a new line of the competing cows. He then proceeds to marshal the cows from the old line to the new one by repeatedly sending either the first or last cow in the (remainder of the) original line to the end of the new line. When he's finished, FJ takes his cows for registration in this new order.

Given the initial order of his cows, determine the least lexicographic string of initials he can make this way.

Input

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single initial ('A'..'Z') of the cow in the ith position in the original line

Output

The least lexicographic string he can make. Every line (except perhaps the last one) contains the initials of 80 cows ('A'..'Z') in the newline.

Sample Input

Sample Output

ABCBCD

Hint

INPUT DETAILS:

FJ has 6 cows in this order: ACDBCB

OUTPUT DETAILS:

Step   Original     New
   #1     ACDBCB
   #2      CDBCB     A
   #3      CDBC      AB
   #4      CDB       ABC
   #5      CD        ABCB
   #6       D        ABCBC
   #7                ABCBCD

题意：

给出一个字符串序列，你可以进行两种操作：将该字符串的第一个字符移入新字符串；将该字符串的最后一个字符移入新字符串。不断进行这两种操作，要求最终输出字典序最小的新字符串。

输入：

第一行为整数N，表示字符串的长度。之后N行每行一个大写字母依次表示原字符串的每一个字符。

输入：

一行，满足条件的新字符串。

分析：

模拟题。定义变量n1和n2分别表示剩余原字符串的首端和尾端，初始时n1=0，n2=N-1.。不断判断剩余字符串与其翻转字符串的字典序大小。如果翻转字符串的字典序大，则输出剩余字符串的第一个字符，如果剩余字符串的字典序大则输出剩余字符串的最后一个字符，若一样大则随便输出首端字符或者尾端字符。注意结果每80个都需要换行。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 const int MAX_N = 3 * 1e4;
 7 int N;
 8 char str[MAX_N + 10];
 9 int compare_reverse(char str[],int i,int j){
10     int ans = -1;
11     for(int ii = 0 ; ii < j - i + 1 ; ii++){
12         if(str[ii + i] < str[j - ii]) return 0;
13         if(str[ii + i] > str[j - ii]) return 1;
14     }
15     return 2;
16 }
17 int main(){
18     scanf("%d",&N); getchar();
19     for(int i = 0 ; i < N ; i++){
20         scanf("%c",&str[i]);
21         getchar();
22     }
23     //printf("%s
",str);
24     int n1 = 0,n2 = N - 1;
25     for(int i = 0 ; i < N ; i++){
26         int k = compare_reverse(str,n1,n2);
27         switch(k){
28             case 0:
29                 printf("%c",str[n1++]);
30                 break;
31             case 1:
32                 printf("%c",str[n2--]);
33                 break;
34             case 2:
35                 printf("%c",str[n1++]);
36                 break;
37         }
38         if(i % 80 == 79) cout << endl;
39     }
40 
41     return 0;
42 }

View Code