文章

1

粉丝

0

获赞

1

访问

5

头像
删除数字 题解:
P1900 华中科技大学2021年机试
发布于2026年1月29日 15:12
阅读数 5

这道题使用两次排序去除最大数字的做法是错误的,比如输入10200 1的测试数据输出的是1000而非正确的最小值200.但是由于垃圾数据点的问题这里仍能通过测试。

正确做法应该是从左往右扫描字符串,维护一个非减部分尽可能长的栈,让较小的数尽可能靠前

#include<bits/stdc++.h>
using namespace std;
int main(){
	stack <char> a;
	int n;
	string s;
	cin>>s>>n;
	for(int i=0;i<s.length();i++){
		while(!a.empty()&&a.top()>s[i]&&n>0){
			a.pop();
			n--;
		}
		a.push(s[i]);
	}
	while(n>0){
		a.pop();
		n--;
	}
	string s1="",ans="";
	while(!a.empty()){
		s1=a.top()+s1; 
		a.pop();
	}
	int zerostart=-1;
	for(int i=0;i<s1.length();i++){
		if(s1[i]!='0'){
			zerostart=i;
			break;
		}
	} 
	if(zerostart==-1){
		ans="0";
	}else{
		for(int i=zerostart;i<s1.length();i++){
			ans+=s1[i];
		}
	}
	cout<<ans;
} 

需要注意的是这个做法中结果在栈中是倒着存的

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发