USACO 2007 November Silver
问题链接：POJ3617 Best Cow Line。
问题简述：输入一个正整数N，再输入N行，每行包含一个字母（'A'-'Z'），将这些字母按顺序构成一个字符串S。按照以下规则取字符，顺序构成一个新的字符串T，T是按照字典顺序最小的。
1.从S的头取一个字符并且删除该字符，连接到T中（开始时T为空串）；
2.从S的尾取一个字符并且删除该字符，连接到T中。
问题分析：这是用一个字符串构建另外一个字符串的问题。比较S的首字符和尾字符，取其小连接到T中即可；当首尾字符相同时，则需要比较下一个，尽量取下一个较小的；当S是一个回文串时，则从哪边取字符结果都是一样的。
程序说明：
使用一个函数test()来比较哪边更小，是一个最为有效的方法，可以使得程序逻辑更加简洁。需要注意的一点是，输出时，每行最多输出80个字符，即每80个字符输出一个换行。
比起使用排序的程序，这个程序要快速一些。
AC的C++语言程序如下：
/* POJ3617 Best Cow Line */#include <iostream>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<n; i++)cin >> a[i];a[n] = '\0';#ifdef DEBUGcout << a << endl;
#endifint start=0, end=n-1, count=0;for(int i=0; i<n; i++) {if(test(a, start, end) == LEFT)cout << a[start++];elsecout << a[end--];if(++count == 80) {count = 0;cout << endl;}}return 0;
}
