字典序最小问题:
给定长度为N的字符串S,要构造一个长度为N的字符串T。起初,T是一个空串,随后反复进行下列任意操作。
从S的头部删除一个字符,加到T的尾部
从S的尾部删除一个字符,加到T的头部
目标是构造字典序尽可能最小的字符串T。
例如S = "ACDBCB" , T = "ABCBCD"
这是一个贪心算法,每次我们都从S的头部或尾部中取较小的一个放到T的末尾,如果相同则继续比较下一个。
code:
#include <cstdio>
#include <cstring>
const int MAXN = 10000+7;
int n;
char str[MAXN];
int main()
{
scanf("%d", &n);
scanf("%s", str);
int b = n - 1;
int a = 0;
while(a <= b)
{
bool left = false;
for(int i=0; a+i <= b; i++)
{
if(str[a+i] < str[b-i])
{
left = true;
break;
}
else if(str[a+i] > str[b-i])
{
left = false;
break;
}
}
if(left) putchar(str[a++]);
else putchar(str[b--]);
}
putchar('\n');
}