11491 - Erasing and Winning（貪心）

11491 - Erasing and Winning（貪心）

一開始真的沒想到這竟然是一道貪心題目。 不過後來仔細想想也就明白了。

我采取的做法是自前向後掃一遍，用一個指針rear動態維護答案數組中的最後一個元素，如果遇到一個比它大的數s[i]，那麼從它開始將它及其它之前的比s[i]小的數全部刪除，並且用變量cnt記錄刪除的個數， 防止刪除多了。

對於貪心算法的正確性我們不難用反證法來證明： 假設這樣做不是最優的，那麼如果不這樣做，對於一個長度一定的答案，得到的結果一定小於這樣做的結果。 但是還有可能少刪了，也就是第三組樣例那種情況，所以我們貪心結束後要確定一下答案的長度，如果答案長了，那麼只要貪心的從最後一個元素開始刪即可，正確性也是不難證明的，因為答案一定是一個非遞增的序列，刪前邊肯定不如刪後邊好。

代碼如下：

#include
using namespace std;
const int maxn = 100000 + 5;
int n,d;
char s[maxn],a[maxn];
int main(){
    while(~scanf(%d%d,&n,&d)){
        if(n==0&&d==0) return 0;
        scanf(%s,s);
        int cnt = 0;
        int rear = 0;
        for(int i=0;ia[rear-1]&&cnt=0;j--){
                    if(a[j]n-d) {
            for(int i=rear-1;i>=0;i--){
                rear--;
                if(rear==n-d) break;
            }
        }
        a[rear] = '';
        printf(%s
,a);
    }
    return 0;
}