题目描述
FJ is about to take his N (1 ≤ N ≤ 30,000) cows to theannual"Farmer of the Year" competition. In this contest every farmerarranges his cows in a line and herds them past the judges.
The contest organizers adopted a new registration scheme thisyear: simply register the initial letter of every cow in the order they willappear (i.e., If FJ takes Bessie, Sylvia, and Dora in that order he justregisters BSD). After the registration phase ends, every group is judged inincreasing lexicographic order according to the string of the initials of thecows' names.
FJ is very busy this year and has to hurry back to his farm, sohe 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. Hethen proceeds to marshal the cows from the old line to the new one byrepeatedly 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 cowsfor registration in this new order.
Given the initial order of his cows, determine the leastlexicographic string of initials he can make this way.
每次只能从两边取，要求取出来之后字典序最小
输入输出格式
输入格式：
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single initial ('A'..'Z') ofthe cow in the ith position in the original line
输出格式：
The least lexicographic string he can make. Every line (exceptperhaps the last one) contains the initials of 80 cows ('A'..'Z') in the newline.
输入输出样例
输入样例#1： 复制
6
A
C
D
B
C
B
输出样例#1： 复制
ABCBCD
说明
每输出80个字符需要输出一个换行。
算法分析：
好在看的是洛谷，巧妙的避开了输出的坑。
分析
构造队列，你可以每次在S中删去头部一个字符，加到T中，也可以在S的尾部删去一个字符加到T中。
挑S的头和尾部字典序列最小的字符：
每次相等时，往里面搜，找到一个能够比出大小的便输出
代码实现：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
using namespace std;
const double eps = 1e-8;
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 1e5 + 10;
const int MAXT = 10000 + 10;
#define N 30105
int main()
{ int n;while(scanf("%d",&n)!=EOF) { char s[N];int sum=0;for(int i=1;i<=n;i++){cin.get();scanf("%c",&s[i]);}int h=1,t=n;while(h<t){if(s[h]<s[t]){printf("%c",s[h++]);}else if(s[h]>s[t]){printf("%c",s[t--]);}else{int x=h,y=t;while(x<y&&s[x]==s[y]) //往里面找{x++;y--;}if(s[x]<s[y]) //比较里面输出当前printf("%c",s[h++]);elseprintf("%c",s[t--]);}sum++;if(sum%80==0)printf("\n");}printf("%c",s[h]);} return 0;
}