专栏文章

题解：UVA11491 奖品的价值 Erasing and Winning

__WHX985_
UVA11491题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqiz1vp
此快照首次捕获于
2025/12/04 05:34
3 个月前
此快照最后确认于
2025/12/04 05:34
3 个月前
查看原文

思路分析

作为一道黄题，暴力搜索是肯定不行的，所以考虑用其他算法。数学好的人可能已经看出这道题用贪心。那么怎么贪心？多举几个例子就会发现，我们可以从开头扫到 n−1n-1 号位，每当一个数小于前一个数就删了，否则删前一个，如果在删掉的中途没次数了就结束整个过程。

估算时间复杂度

扫一遍时间复杂度为 O(n)O(n)，再查找一遍时间复杂度为 O(n−k)O(n-k)，所以总时间复杂度为 O(2n−k)O(2n-k)。

易错点

代码停止条件易错，请务必认真仔细。

代码实现

AC 代码
CPP
#include<bits/stdc++.h>
#define WHX985 return
#define code 0
using namespace std;
int f[1000005];
bool vis[1000005];
int main(){
	while(1){
		int n,k;
		cin>>n>>k;
		if(n==0&&k==0){
			return 0;
		}
		string a;
		cin>>a;
		for(int i=0;i<=a.size()-1;i++){
			f[i]=a[i]-'0';
			vis[i]=0;
		}
		int jk=0;
		for(int i=0;i<=a.size()-1;i++){
			if(jk==k-1)break;
			if(vis[i]){
				continue;
			}
			if(f[i+1]<f[i]){
				jk++;
				vis[i+1]=1;
			}else{
				jk++;
				vis[i]=1;
			}
		}
		int nao=0x7ffffff,minn;
		for(int i=0;i<a.size();i++){
			if(vis[i])continue;
			if(nao>f[i]){
				nao=f[i];
				minn=i;
			}
		}
		vis[minn]=1;
		for(int i=0;i<=a.size()-1;i++){
			if(!vis[i]){
				cout<<f[i];
			}
		}
		cout<<'\n';
	}
	
	WHX985 code;
}
//100000
//587854740865
// 8 8  7 0865
//8874086

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...