UVa 11491 - Erasing and Winning(贪心)

给出一个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博客 ,格式可能有所偏差。

支付宝扫码领红包