UVa 11491 - Erasing and Winning（贪心）

发表于 分类于 ， Disqus：

给出一个n个数字的串，去掉d个数字使得串的数值最大。

用贪心法解决，当前一个的数字小于后一个数字时，前一个即被去掉，当去掉个数足够时，读入剩下的字符即可。如果去掉的数目不够，剩下的数字则不存入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>
#include<vector>
using namespace std;
vector<char> s;
int main(){
    int n,d;
    while(~scanf("%d%d",&n,&d)&&n){
        int len=n-d;
        s.clear(),getchar();
        for(int i=0;i<n;++i){
            char c=getchar();
            if(s.size()>0){
                int p=(int)s.size()-1;//从最后一个字符开始判断是否去除。
                while(d&&c>s[p]&&p>=0){
                    s.erase(s.begin()+p--);
                    --d;
                }
            }
            if(s.size()!=len) s.push_back(c);//字符数目未满，继续存入。
            else --d;
        }
        for(int i=0;i<s.size();++i) putchar(s[i]);
        printf("\n");
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章