题目链接:https://codeforces.ml/problemset/problem/1765/N

删数问题,存在0元素,且首位不能为0,求删除k个数后的最小值为多少。

思路:删数问题一般跑不了贪心。因为我们总应该要贪婪的选择删除前面的数,将靠前的大数消灭掉。
我们需要解决的是冲突问题  存在  90000123  900123  ,如果删除三个数,那么两个数的删除的手段是不同的。

考虑使用邻接表来存储每个数字所在的位置。我们需要保留n-k个数。第一个需要保留的一定不能是0,所以我们从1开始考虑1的位置是否符合,然后找到符合的,对于之后的任意删除这个位置之前的所有元素。继续判断即可。同时不断的更新保留后的最后位置,和k的值(这里比较恶心,需要处理一些边界问题)。


code:

void solve()
{
	string s;
	cin>>s;
	int k;
	cin>>k;
	int n = s.size();
	vector<vector<int>> ve(10);
	for(int i=0;i<n;i++)//存储位置
		ve[s[i]-'0'].push_back(i);
	for(int i=0;i<10;i++)//对位置进行反向
		reverse(ve[i].begin(),ve[i].end());
	string ans;
	int lst = 0,len = n-k;
	for(int i=0;i<len;i++){//我们想要len个数
		for(int d = (i==0);d<=9;d++){//然后来看我们需要保留的数,如果是首位,那么我们不必考虑0
			while(!ve[d].empty()&&ve[d].back()<lst)//这个数之前的我们不能取了,因为我们需要保证有序
				ve[d].pop_back();
			if(!ve[d].empty()&&ve[d].back()-lst<=k){//这时来看一下,我们取的满不满足范围
				ans+=d+'0';
				k-=ve[d].back()-lst;//里面的数都删了
				lst = ve[d].back()+1;
				break;
			}
		}
	}
	cout<<ans<<endl;
}