原题链接:http://poj.org/problem?id=3617
基本思想:不断取S的开头和末尾中较小的一个字符放到T的末尾
难点:开头和末尾的字符相同的情形如何解决
修正算法:按照字典序比较S和S反转后的字符串S’
#include <iostream>
#include<cstdio>
using namespace std;
//const int MAX_N=2000;
//输入
int n;
char s[2100];
void solve()
{
//剩余字符串为s[a],s[a+1],……s[b];
int a=0,b=n-1;//N-1?????!!!!
int cnt=1;
bool left=false;
while(a<=b)
{
//将从左起和从右起的字符串进行比较
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++]);
if(cnt==80)
{
putchar('\n');
cnt=0;
}
cnt++;
}
else
{
putchar(b--);
if(cnt==80)
{
putchar('\n');
cnt=0;
}
cnt++;
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>s[i];
}
solve();
cout << endl;
return 0;
}