poj 3617 Best Cow Line 解题报告

题目链接：http://poj.org/problem?id=3617

题目意思：给出一条长度为n的字符串S，目标是要构造一条字典序尽量小，长度为n的字符串T。构造的规则是，如果S的头部的字母 < S的尾部的字母，那么将S的头部的字母加入到T中，删除S的头部的字母；如果S的头部的字母 > S的尾部的字母，那么将S的尾部的字母加入到T中，删除S的尾部的字母。

　　这个题目的关键是如何处理 S 的头部的字母（假设用 i 指示） = S的尾部的字母(j) 这种情况。此时需要比较 i+1 和 j-1 的位置的字母，如果相同，继续比较下去。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 using namespace std;

 const int maxn =  + ;

 char s[maxn];

 int main()

 {

     int n, i, j, a, b, cnt;

     while (scanf("%d", &n) != EOF)

     {

         for (i = ; i < n; i++)

         {

             getchar();

             scanf("%c", &s[i]);

         }

         cnt = ;

         i = , j = n-;

         while (i <= j)

         {

             if (s[i] < s[j] && i <= j)

                 printf("%c", s[i++]);

             else if (s[i] > s[j] && i <= j)

                 printf("%c", s[j--]);

             else

             {

                 a = i;

                 b = j;

                 while (s[i] == s[j] && i < j)

                 {

                     i++;

                     j--;

                 }

                 if (s[i] <= s[j] || i == j)  // s[i] <= s[j] 不能写成s[i] < s[j]，这是为了处理aaaaa这些情况，否则改了会输出a

                 {

                     printf("%c", s[a]);

                     j = b;

                     i = a+;

                 }

                 else if (s[i] > s[j])

                 {

                     printf("%c", s[b]);

                     i = a;

                     j = b-;

                 }

                 printf("a = %d, b = %d, i = %d, j = %d\n", a, b, i, j);

             }

             cnt++;

             if (cnt %  == )

                 putchar('\n');

         }

     }

     return ;

 }

　　相反，别人写的，不需要考虑太多琐碎的情况

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 using namespace std;

 const int maxn =  + ;

 char s[maxn];

 int main()

 {

     int n, i, a, b;

     while (scanf("%d", &n) != EOF)

     {

         for (i = ; i < n; i++)

         {

             getchar();

             scanf("%c", &s[i]);

         }

         int cnt = ;

         a = , b = n-;

         while (a <= b)

         {

             bool left = false;

             for (i = ; a + i <= b; i++)

             {

                 if (s[a+i] < s[b-i])

                 {

                     left = true;

                     break;

                 }

                 else if (s[a+i] > s[b-i])

                 {

                     left = false;

                     break;

                 }

             }

             if (left)

                 printf("%c", s[a++]);

             else

                 printf("%c", s[b--]);

             cnt++;

             if (cnt %  == )

                 putchar('\n');

         }

     }

     return ;

 }

poj 3617 Best Cow Line 解题报告的相关教程结束。