Best Cow Line

最近彩虹岛上发生了一个可怕的事件，大魔王ZZY为了督促彩虹岛的岛民好好训练，把每个人的电子设备都给加了一个密码，英勇的彩虹岛岛民要和大魔王作斗争，于是迫使大魔王说出了一个长度为N(1≤N≤2000)的字符串S，然而最后的密码是由S中所有字母构成字典序最小的字符串T（起初T是一个空串）。但是要想知道最后的密码只能以下两种操作： ·从S的头部删除一个字符，加到T的尾部

·从S的尾部删除一个字符，加到T的尾部

目标是要构造字典序尽可能小的字符串

Input 第一行一个整数N（代表字符串S的长度） 接下来的2~N+1行是字符串S中的字母（只包含大写字母） Output 输出时每行最多80个字符

Sample Input

6 A C D B C B

Sample Output

ABCBCD

CODE:

#include <iostream> using namespace std; int main() { int n,i; char a[2200],b[2200]; cin>>n; for(i=1; i<=n; i++) { cin>>a[i]; } int h,t,e=1; h=1; t=n; while(h!=t) { if(a[h]>a[t]) { b[e++]=a[t]; t--; } else if(a[h]<a[t]) { b[e++]=a[h]; h++; } else if(a[h]==a[t]) //遇到两个字符相等时，比较下一个，直到两个字符不相等时，输出较小的一端的一个字符。 { int hh=h,tt=t; while(a[hh]==a[tt]) { hh++; tt--; } if(a[hh]<a[tt]) { b[e++]=a[h]; h++; } else if(a[hh]>a[tt]) { b[e++]=a[t]; t--; } } } b[e++]=a[h]; for(i=1;i<e;i++) { cout<<b[i]; if(i%80==0) cout<<endl; } return 0; }