POJ3617 Best Cow Line

问题链接：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 DEBUG    cout << a << endl;#endif    int start=0, end=n-1, count=0;    for(int i=0; i<n; i++) {        if(test(a, start, end) == LEFT)            cout << a[start++];        else            cout << a[end--];        if(++count == 80) {            count = 0;            cout << endl;        }    }    return 0;}