题目大意：给定长度为N的字符串S，要构造一个长度为N的字符串T。起初，T是一个空串，随后反复进行下列任意操作。
从S的头部删除一个字符，加到T的尾部
从S的尾部删除一个字符，加到T的尾部
目标是构造字典序尽可能小的字符串。
题目分析；从字典序的性质上看，无论T的末尾有多大，只要前面部分较小就可以。所以我们可以试一下如下贪心算法：
不断取S和T的末尾中较小的一个字符放到T的末尾
这个算法已经接近正确了，只是针对S的开头和末尾字符相同的情形还没有定义。在这种情况下，因为我们希望能够尽早使用更小的字符，所以就要比较一下下一个字符的大小。下一个字符也有可能相同，因此就有如下算法：
按照字典序比较字符串S和S反转后的字符串S'。
如果S较小，就从S的开头取出一个文字，放到T的末尾。
如果S'较小，就从S的末尾取出一个文字，放到T的末尾。
（若果相同则去哪一个都可以）
#include <cstdio>
char s[2002], tmp[2];
int n;
int main() {
while(~scanf("%d", &n)) {
for(int i=0;i<n;i++) {
scanf("%s", tmp);
s[i] = tmp[0];
}
int l = 0, r = n - 1, cnt = 0;
while(l <= r) {
int i = 0, left = true;
while(l + i <= r - i) {
if(s[l+i] < s[r-i]) {
break;
}
if(s[l+i] > s[r-i]) {
left = false;
break;
}
i ++;
}
if(left == true) putchar(s[l++]);
else putchar(s[r--]);
cnt ++;
if(cnt % 80 == 0) putchar('\n');
}
if(cnt % 80) putchar('\n');
}
return 0;
}
posted on 2015-02-11 15:59
JulyRina 阅读(2205)
评论(0) 编辑 收藏 引用 所属分类:
解题报告