题解 P6140 【[USACO07NOV]Best Cow Line S】

题意

多组测试数据。

给你一个长度为N的字符串S,输入格式是依次输入N个字符。

N <= 2000。

每次你可以从S的开头或者结尾取出一个字符,放到一个T字符串的尾部。

输出字典序最小的T字符串,每80个字符换一行输出。

题解

不难，直接循环即可。但是输出略微毒瘤。

我们可以把情况分为两种：

两边字符不一样——直接把字典序小的拿出。

两边字符一样——继续寻找，找到不一样的，然后把字典序小的一边先拿出。

代码

#include<iostream>
#include<cstring>
using namespace std;
int n;
int suml,sumr,sum;
char a[30001],ans[30001];
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	while(strlen(a)!=strlen(ans))
	{
		int l,r;
		r=strlen(a)-1-sumr;
		l=suml;
		while(l<r&&a[l]==a[r]) l++,r--;
		if(a[l]>a[r]) //第一种情况
        sumr++,ans[strlen(ans)]=a[strlen(a)-sumr];
		else suml++,ans[strlen(ans)]=a[suml-1];//否则，判断
	}
	for(int i=0;i<strlen(ans);i++)
	{
		cout<<ans[i];
		sum++;
		if(sum==80) sum=0,cout<<endl;//输出判断
	}
}