https://vjudge.net/problem/POJ-3617
题目简单理解就是:
给定长度为N的字符串为S,要构造一个长度为N的字符串T。起初,T 是一个空串,随后反复进行下列任意操作。
①:从S的头部删除一个字符串,加到T的尾部,
②:从S的尾部删除一个字符,加到T的尾部
目标是要构造字典序尽可能小的字符串T。(字典序是指从前到后比较两个字符串大小的方法。首先比较第1个字符,如果不同则第1个字符较小的字符串更小,如果相同则继续比较第2个字符.......如此继续,来比较整个字符串的大小)
限制条件:
1<=N<=2000
字符串S只包含大写英文字母.
输入样例:
6
ACDBCB
输出样例:
ABCBCD
分析:
从字典序的性质来看,不管字符串T的尾部有多大,只要前面够小就可以,所以我们可以采用贪心算法
①:不断去D开头和尾部中较小的一个字符放到T的尾部
②:针对开头和尾部字符相同的情况,我们希望能够尽早使用更小的字符,所以就要比较下一个字符的大小。下一个字符也有可能相同。
因此:
按照字典序比较S和将S反转后的字符串S'
如果S较小,就从S的开头取一个字符,追加到T尾部
如果S'较小,就从S的尾部取出一个字符,追加到T尾部。
如果相同则取哪个都可以。
代码:
#include<iostream>
using namespace std;
#define MAX 2000
char S[MAX+1];
int main ()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> S[i];
int a = 0, b = n - 1;
while (a <= b)
{
bool vis = false;
for (int i = 0; i + a <= b; i++)
{
//从字符串的头和尾作比较
if (S[a + i] < S[b - i])
{
vis = true;
break;
}
if (S[a + i] > S[b - i])
{
vis = false;
break;
}
}
if (vis)
cout << S[a++];
else
cout << S[b--];
}
cout << endl;
return 0;
}