POJ 3617 - Best Cow Line

http://poj.org/problem?id=3617

概要

N 個の大文字のアルファベットの列が与えられる．

ここから先頭か末尾の文字を1つずつ取り出して並べたとき，最も辞書順が小さくなる文字列を答える．

制約

• 1 <= N <= 2000
• 答えは80文字ずつ改行で区切って出力する．

解法

アルファベットの列を s とする．

i 番目から j 番目の部分列について考えているとき，s[i+k] != s[j-k] なる k について，

• s[i+k] < s[j-k] なら先頭の文字をとる
• s[i+k] > s[j-k] なら末尾の文字をとる

と貪欲にとっていけば最悪 O( N^2 ) で解ける．

もしそのような k が無いときは，つまり s の i 番目から j 番目までの文字がすべて同じなので，どちらをとっても変わらない．

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   int N;
 7   scanf("%d", &N);
 8   static char s[30001];
 9   for (int i = 0; i < N; i++) {
10     scanf("%1s", &s[i]);
11   }
12 
13   static char buf[30001];
14   char *p = buf;
15   for (int beg = 0, end = N-1; beg <= end;) {
16     int b = beg, e = end;
17     while (b <= e && s[b] == s[e]) {
18       b++;
19       e--;
20     }
21     if (s[b] <= s[e]) {
22       *p++ = s[beg++];
23     } else {
24       *p++ = s[end--];
25     }
26   }
27   for (int i = 0; i < N; i += 80) {
28     for (int j = 0; j < 80 && i+j < N; j++) {
29       putchar(buf[i+j]);
30     }
31     putchar('\n');
32   }
33   return 0;
34 }