JulyRina's blog
welcome to July Rina's blog
posts - 22,comments - 1,trackbacks - 0
题目大意:给定长度为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 阅读(2203) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理