本文主要是介绍poj 3623 Best Cow Line, Gold(贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
从旧的一串字符串中从头或者从尾取数，排列成一个新串，使得新串的字典序最小。
解题思路：
很明显，这是一个贪心，用了暴力求解。
标记两个数，l 和 r 分别表示头和尾的下标。如果头部的字典序小，那么输出头部的，如果尾部的字典序小，那么输出尾部的。如果他们两个是相同的字符，那么继续往下找，直到找到第一个不相等的，或者头下标大于等于尾下标（此时，说明字符串对称，随便输出一个），输出字典序较小所在的一侧的一个字符，一定是一个字符。（一开始直接输出一堆，自以为是个优化，结果wa死。例如数据：AABAABAAA，如果不是一个一个输出，结果是AAAABAAAB，但实际结果应该是AAAAABAAB。因为在输出的一段字符的时候，不能保证这一段字符一定是字典序最小的，妈蛋，果然还是年轻）。
哦，这题还有一个坑点：每80个字符要换一行，如果最后一行不是刚刚换过行，也要换行。
代码如下：
代码简直不是一般性的丑。。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{int n,i,j,l,r;char a[30009];while(scanf("%d",&n)==1){for(i=1; i<=n; i++){scanf(" %c",&a[i]);}a[0]='Z'+1;a[n+1]='Z'+2;l=1;r=n;int xx=0;while(l<=r){if(a[l]<a[r]){if(xx>=80){printf("\n");xx=0;}printf("%c",a[l]);xx++;l++;}else if(a[l]>a[r]){if(xx>=80){printf("\n");xx=0;}printf("%c",a[r]);xx++;r--;}else if(a[l]==a[r]){int cnt = 1;int tl = l;int tr = r;while(a[tl+1]==a[tr-1]&&tl+1<tr-1){tl++;tr--;cnt++;}if(a[l+cnt]<=a[r-cnt]){if(xx>=80){printf("\n");xx=0;}printf("%c",a[l]);xx++;l++;}else if(a[l+cnt]>a[r-cnt]){if(xx>=80){printf("\n");xx=0;}printf("%c",a[r]);xx++;r--;}}}printf("\n");}return 0;
}
这篇关于poj 3623 Best Cow Line, Gold(贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
