Description

 键盘输入一个高精度的正整数n(≤100位),去掉其中任意s个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的n与s,寻找一种方案,使得剩下的数字组成的新数最小。

Input

输入两个数字,分别为原始数n,要去掉的数字数s (s < n)。

Output

 输出去掉s个数后最小的数

Sample

Input 

178543  4

Output 

13

很容易感觉是一道很简单贪心的题(就从大数开始删),但问题就在于高位数的删除权重要高于低位数 ,例如 6139   删除一个数,肯定是删除6而不是9

观察到这一点之后,我们再往深想一点,就是要维持在尽量删除左边数的情况下删除掉大数。

我们可以从左向右开始找,找一个大数,这个大数是什么样的? 一个要大于之前所有数的数。这样的数找到后,身后的数一定比它小

这样我们就从左到右,从升序开始找,找到第一个逆序对然后删除,然后继续找一个逆序对。知道删除的数量为s



#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a;
	int s,i;
	cin>>a>>s;
	while(s--)
	{
		i=0;
		while(a[i]<=a[i+1])
			i++;
		a.erase(i,1);
	}
	int flag = 0;
	for(int i=0;i<a.size();i++)
	{
		if(a[i]=='0'&&i<a.size()-1&&flag == 0)
			continue;
		else
		{
			cout<<a[i];
			flag = 1;
		}
	}
}