首页 > 代码库 > POJ3617-Best Cow Line
POJ3617-Best Cow Line
给定长度为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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。