• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            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 閱讀(2235) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告
            亚洲精品综合久久| 久久亚洲中文字幕精品一区| 久久婷婷成人综合色综合| 久久婷婷激情综合色综合俺也去| 99久久人妻无码精品系列蜜桃| AAA级久久久精品无码区| 午夜精品久久影院蜜桃| 久久国产精品77777| 无码任你躁久久久久久| 丁香狠狠色婷婷久久综合| 伊人久久大香线蕉AV一区二区| 精品蜜臀久久久久99网站| 亚洲午夜精品久久久久久app| 久久99亚洲网美利坚合众国| 怡红院日本一道日本久久| 亚洲精品成人久久久| 国产精品99久久久久久猫咪 | 久久伊人中文无码| 99麻豆久久久国产精品免费| 久久这里只有精品首页| 午夜精品久久久久久久无码| 国产精品亚洲美女久久久| 91久久精品91久久性色| 一本色道久久综合亚洲精品| 国产69精品久久久久观看软件| 国产福利电影一区二区三区久久老子无码午夜伦不 | 精品熟女少妇aⅴ免费久久| 久久精品aⅴ无码中文字字幕不卡| 人妻无码久久精品| 日日狠狠久久偷偷色综合96蜜桃| 久久国产精品成人免费| 精品久久久久久无码专区不卡| 久久丫精品国产亚洲av| 亚洲va中文字幕无码久久不卡 | av国内精品久久久久影院| 欧美黑人又粗又大久久久 | 国产精品永久久久久久久久久| 久久国产精品国产自线拍免费| 国产精品毛片久久久久久久| 久久精品国产免费| 精品无码久久久久久国产|