限制条件:
1<=N<=2000
字符串都在大写字符
样例:
输入
N=8
ADHCACBD
输出
ADBCACDH
解题分析:
看到这个问题,首先你肯定不难想到:每次都从S的头部或尾部选择最小的字符放到T的尾部
对,这已经很接近真实了,但是还没考虑首部和尾部相同的情况,那么首部和尾部相同的情况下该取首部还是尾部呢?
其实思路还是一样的,如果首部A和尾部B相同,就取首部的下一个字符(也就是第2个字符,设为A’)和尾部的前一个字符(也就量倒数第2个字符,设为B’)比较,如果A’<B’,则取首部;否则取尾部。如果A’和B’还相同,再比较A’的后一个字符A’’和B’的前一个字符B’’,以此类推直到S字符串为空。基于这个思路可以写出以下程序:
#include <stdio.h>
#include <tchar.h>
#include <queue>
#include "iostream"
using namespace std;
const int N = 8;
char chs[N+1] = "ADHCACBD";
char* solve(char chs[])
{
int start = 0, end = N - 1;
bool isLeft = false;
char dest[N];
while(start <= end) {
for(int i = 0; start + i < end; i ++)
{
if(chs[start + i] < chs[end - i])
{
isLeft = true;
break;
}
else if(chs[start + i] > chs[end -i])
{
isLeft = false;
break;
}
else
continue;
}
if(isLeft)
{
dest[N-(end - start + 1)] = chs[start ++];
//putchar(chs[start ++]);
}
else
{
dest[N-(end - start + 1)] = chs[end --];
//putchar(chs[end --]);
}
}
return dest;
}
int main() {
char *result = solve(chs);
for(int i=0; i<N; i++)
{
putchar(result[i]);
}
return 0;
}