A21669.删数问题 题解

贪心题。

贪心思路：从高位向低位遍历每一位，若第 $i+1$ 位比第 $i$ 位小，则删除第 $i$ 位
原理：让高位尽可能小。
误区：很多人认为每次删最大的数（最开始我也是），原理我上面也已经说到了，举个反例：
$n=1324,k=1$
错误方法：$1324\xrightarrow{删4\ }132$
正确方法：$1324\xrightarrow{删3\ }124$

Code:

#include <bits/stdc++.h>
using namespace std;
int main(){
	int k;
	string n;
	cin>>n>>k;
	for (int i=1;i<=k;i++){
		for (int j=0;j<n.size();j++){
			if (n[j]>n[j+1]){//要删除
				n.erase(j,1);
				break;//删完一次记得break
			}
		}
	}
    if (n.size()==1){
        cout<<n;
        return 0;
    }
	for (int i=n.find_first_not_of('0');i<n.size();i++) cout<<n[i];//不输出前导0
	return 0;
}