题目不算难,但是不认真想的话很容易wa,我就是wa了多次才意识到自己想法存在的缺陷。
相同的时候往后找知道出现不相同时,只能判断出当前字符的优先顺序。
这个题目如果朴素的按照这种方法做的话复杂度其实是n*n的,可是数据较弱,可以过,我用的就是朴素的办法。
但是多加思索的话可以发现我们可以用后缀数组保存原串和反串,使复杂度降低到nlongn。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=3e4+9;
char a[maxn],ans[maxn];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
char tmp[10];
scanf("%s",tmp);
a[i]=tmp[0];
}
int st=1,ed=n,lon=0;
while(st<=ed)
{
if(a[st]<a[ed])
ans[++lon]=a[st++];
else if(a[st]>a[ed])
ans[++lon]=a[ed--];
else
{
int s=st,t=ed;
while(s<=t&&a[s]==a[t])
{
s++;
t--;
}
if(s>t||a[s]<a[t])
ans[++lon]=a[st++];
else
ans[++lon]=a[ed--]; }
}
for(int i=1;i<=lon;i++)
{
printf("%c",ans[i]);
if(i%80==0)
printf("\n");
}
if(n%80)
printf("\n");
}
return 0;
}