POJ 3617 Best Cow Line

【题意简述】：就是给定一个长度为N的字符串S,yao构造一个长度为N的字符串t。起初，T是一个空串，随后反复进行下列任一操作。

1、从S的头部删除一个字符，加到T的尾部。

2、从S的尾部删除一个字符，加到T的尾部。

现在让我们构造字典序尽可能小的字符串T。

【思路】：思路很好建立，就是简单的贪心，我们可以一次的将S的头部与尾部的元素进行比较，小的加到T的尾部。

这样就解决了！具体实现，详见代码！

#include<iostream>
using namespace std;
#define MAX_N 2005

int N;
char S[MAX_N+1];

void solve()
{
	int count = 1;
	int a = 0,b = N-1;
	while(a <= b)
	{
		bool left = false;
		for(int i = 0;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) putchar(S[a++]);
		else putchar(S[b--]);
		// PE????80???????????У? 
		count++;
		if(count>80){
			cout<<endl;
			count = 1;
		}
			
	}
}

int main()
{
	cin>>N;
	for(int i = 0;i<N;i++)
		cin>>S[i];
	solve();
	return 0;
}

POJ 3617 Best Cow Line,布布扣,bubuko.com

POJ 3617 Best Cow Line

原文：http://blog.csdn.net/u013749862/article/details/23291717