题目链接

Best Cow Line POJ - 3617

思路

贪心策略如下：

1。左端小取左

2。右端小取右

3。左右相同则比较次左与次右，规则同1。2。

注意：本题输出要求每隔80个字符换行

时间复杂度

$$ O(N^2) $$

代码

#include <cstdio>

using namespace std;

const int MAXN = 2000 + 10;

char buf[5];
char s[MAXN];

bool check(int l, int r) {
    for (int i = l; i <= r; i++) {
        if (s[i] < s[r - (i - l)]) {
            return true;
        } else if (s[i] > s[r - (i - l)]) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    scanf("%d", &n);// don't forget &
    for (int i = 1; i <= n; i++) {
        scanf("%s", buf);// no &
        s[i] = buf[0];
    }
    int l = 1, r = n;
    int index = 0;
    while (l <= r){
        if (check(l, r)) {
            putchar(s[l]);
            l++;
        } else {
            putchar(s[r]);
            r--;
        }
        index++;        
        if (index % 80 == 0) {
            puts("");
        }
    }
    return 0;
}