題目大意：給定長度為N的字符串S，要構(gòu)造一個(gè)長度為N的字符串T。起初，T是一個(gè)空串，隨后反復(fù)進(jìn)行下列任意操作。
從S的頭部刪除一個(gè)字符，加到T的尾部
從S的尾部刪除一個(gè)字符，加到T的尾部
目標(biāo)是構(gòu)造字典序盡可能小的字符串。
題目分析；從字典序的性質(zhì)上看，無論T的末尾有多大，只要前面部分較小就可以。所以我們可以試一下如下貪心算法：
不斷取S和T的末尾中較小的一個(gè)字符放到T的末尾
這個(gè)算法已經(jīng)接近正確了，只是針對S的開頭和末尾字符相同的情形還沒有定義。在這種情況下，因?yàn)槲覀兿Ｍ軌虮M早使用更小的字符，所以就要比較一下下一個(gè)字符的大小。下一個(gè)字符也有可能相同，因此就有如下算法：
按照字典序比較字符串S和S反轉(zhuǎn)后的字符串S'。
如果S較小，就從S的開頭取出一個(gè)文字，放到T的末尾。
如果S'較小，就從S的末尾取出一個(gè)文字，放到T的末尾。
（若果相同則去哪一個(gè)都可以）
#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 閱讀(2250)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告