首页 > 代码库 > POJ3617-Best Cow Line

POJ3617-Best Cow Line

2024-07-25 05:29:58   215人阅读

给定长度为N的字符串S，构造长度为N的字符串T，起初T是空串，反复从S的头部或者尾部删除一个字符，加到T的尾部。目标是构造字典序尽可能小的T。尝试如下贪心算法：

  • 不断取S头部和尾部较小的字符放到T的尾部。

考虑S头部和尾部字符相同的情况。有如下算法：

  • 按照字典序比较S和将S反转后的字符串S‘；
  • 如果S较小，从S的头部取出一个字符添加到T尾部；
  • 如果S‘较小，从S’的头部（即S的尾部）取出一个字符添加到T的尾部。
 1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4  5 int N; 6 char S[2100]; 7  8 void solve() 9 {10     int left = 0, right = N-1;11     bool left_flag = false;12 13     while (left <= right)14     {15         for (int i = 0; left+i <= right; i++)16         {17             if (S[left+i] < S[right-i])18             {19                 left_flag = true;20                 break;21             }22             else if (S[left+i] > S[right-i])23             {24                 left_flag = false;25                 break;26             }27         }28         if (left_flag) putchar(S[left++]);29         else putchar(S[right--]);30     }31     putchar(‘\n‘);32 }33 34 int main()35 {36     cin >> N;37     for (int i = 0; i < N; i++)38         cin >> S[i];39 40     solve();41 42     return 0;43 }

 

POJ3617-Best Cow Line


联系
我们