POJ 3617 Best Cow Line 字典序贪心

给定一个长度为N的字符串S,要构造一个长度为N的字符串T.

起初，T是一个空串，随后反复进行下列任意操作：

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

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

目标是要构造字典序尽可能小的字符串T。

《挑战》书上的原题，贪心嘛。很明显的。

但是，（在我的代码上总有意外？？？），在比较头尾两个字符的时候，碰见相等的字符，需要继续比较各自下一位字符。在这里，我T了好几次？？还以为输入输出出问题，没想到是：如果两个字符继续相等，相等，相等，最后还是相等，或者被迫退出的时候，就随便选头部或尾部的字符就行了。

比如：

这个样例。


//POJ 3617 字典序贪心 
#include<iostream>
#include<algorithm>
#include<set>
#include<cstring>
#include<queue>
#include<stack>
#include<stdio.h>
#include<vector>
using namespace std;
#define ll long long
const int maxn=2100;
char s[maxn];
char t[maxn];

int main()
{
	int n;
	scanf("%d",&n);
	getchar();
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
	}

	int left=1;
	int right=n;
	int cnt=1;
	while(left<=right)
	{
		int l=left,r=right;
		while(s[l]==s[r] && l<=r)
		{
		//	cout<<l<<" "<<r<<endl;
			l++;r--;
		//	cout<<l<<" "<<r<<endl;
		}
		if(s[l]<=s[r])//害惨我也！ 
		{
		//	t[cnt++]=s[left++];
			putchar(s[left++]);
			cnt++;
		}
		else if(s[r]<s[l])
		{
		//	t[cnt++]=s[right--];
			putchar(s[right--]);
			cnt++;
		}
		if(cnt%80==1)
			putchar('\n');
		
	}

	return 0;
 }

放一下书上的原码：


//AC
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAX_N = 2000+100;
int N;
char S[MAX_N+1];
vector<char> vec;


void solve()
{
	int cnt=0;
	int l=1,r=N;
	while(l<=r)
	{
		bool left=false;
		for(int i=0;l+i<=r;i++)
		{
			if(S[l+i]<S[r-i])
			{
				left=true;
				break;
			}
			if(S[l+i]>S[r-i])
			{
				left=false;
				break;
			}
		}
		if(left) putchar(S[l++]);
		else putchar(S[r--]); 
		cnt++;
		if(cnt%80==0)
			putchar('\n');
	}
}

int main()
{
	scanf("%d",&N);
	getchar();
	for(int i=1;i<=N;i++)
		cin>>S[i];
	
	solve();
	
}

。。。

POJ 3617 Best Cow Line 字典序贪心

相关推荐