一開始真的沒想到這竟然是一道貪心題目。 ?不過后來仔細想想也就明白了。 我采取的做法是自前向后掃一遍，用一個指針rear動態維護答案數組中的最后一個元素，如果遇到一個比它大的數s[i]，那么從它開始將它及其它之前的比s[i]小的數全部刪除，并且用變量cnt記錄刪除的個數， 防止刪除多了。 對于貪心算法的正確性我們不難用反證法來證明： 假設這樣做不是最優的，那么如果不這樣做，對于一個長度一定的答案，得到的結果一定小于這樣做的結果。 但是還有可能少刪了，也就是第三組樣例那種情況，所以我們貪心結束后要確定一下答案的長度，如果答案長了，那么只要貪心的從最后一個元素開始刪即可，正確性也是不難證明的，因為答案一定是一個非遞增的序列，刪前邊肯定不如刪后邊好。 代碼如下： ~~~ #include<bits/stdc++.h> 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;i<n;i++){ if(s[i]>a[rear-1]&&cnt<d) { for(int j=rear-1;j>=0;j--){ if(a[j]<s[i]&&cnt<d) { rear--; cnt++; } else break; } a[rear++] = s[i] ; } else a[rear++] = s[i] ; } if(rear>n-d) { for(int i=rear-1;i>=0;i--){ rear--; if(rear==n-d) break; } } a[rear] = '\0'; printf("%s\n",a); } return 0; } ~~~