P1106 删数问题

Miku

---

一个很好证明的贪心，从左往右，依次删掉比右边的数大的数，如果还需要删，就从后往前删

---

注意，这个题要考虑前导零

---

#include<iostream>
#include<stack>
using namespace std;
string n;int k;
bool vis[260];
stack<int> s;
int f;
int main(){
	cin>>n;
	cin>>k;
	int l=n.length();
	for(int i=0;i<l;++i){
		if(s.empty()||n[s.top()]<=n[i]){
			s.push(i);
			continue;
		}
		while(!s.empty()&&n[s.top()]>n[i]&&k){
			vis[s.top()]=1;
			s.pop();
			k--;
			if(k==0){
				f=1;
				break;
			}
			
		}
		if(f)
		break;
		s.push(i);
	}
	int i=l-1;
	while(k){
		while(vis[i])
		i--;
		vis[i]=1;
		k--;
	}
	f=0;
	for(int i=0;i<l;++i){
		if(!vis[i]){
		if(n[i]=='0'&&f==0){
			continue;
		}
		f=1;
		cout<<n[i];
		}
	}
	if(!f)
	cout<<0;
	return 0;
}