USACO 2007 November Silver

问题链接：。

问题简述：输入一个正整数N，再输入N行，每行包含一个字母（'A'-'Z'），将这些字母按顺序构成一个字符串S。按照以下规则取字符，顺序构成一个新的字符串T，T是按照字典顺序最小的。

1.从S的头取一个字符并且删除该字符，连接到T中（开始时T为空串）；

2.从S的尾取一个字符并且删除该字符，连接到T中。

问题分析：这是用一个字符串构建另外一个字符串的问题。比较S的首字符和尾字符，取其小连接到T中即可；当首尾字符相同时，则需要比较下一个，尽量取下一个较小的；当S是一个回文串时，则从哪边取字符结果都是一样的。

程序说明：

使用一个函数test()来比较哪边更小，是一个最为有效的方法，可以使得程序逻辑更加简洁。需要注意的一点是，输出时，每行最多输出80个字符，即每80个字符输出一个换行。

比起使用排序的程序，这个程序要快速一些。

AC的程序如下：

/* POJ3617 Best Cow Line */#include 
    
     using namespace std;//#define DEBUGconst int LEFT = 1;const int RIGHT = 2;const int MAXN = 2000;char a[MAXN+1];int test(char s[], int start, int end){    while(start < end) {        if(s[start] < s[end])            return LEFT;        else if(s[start] > s[end])            return RIGHT;        start++;        end--;    }    return LEFT;}int main(){    int n;    cin >> n;    for(int i=0; i
     
      > a[i];    a[n] = '\0';#ifdef DEBUG    cout << a << endl;#endif    int start=0, end=n-1, count=0;    for(int i=0; i