信息学奥赛一本通 1321：【例6.3】删数问题(Noip1994)

题目链接：点击这里

那么刚拿到这道题如何去思考呢？我们可以先试着找规律。

如果要从178543中取出1个数，使这个数最小，应该取……8

如果要从17543中取出1个数，使这个数最小，应该取……7

如果要从1543中取出1个数，使这个数最小，应该取……5

……

可以发现：1，7，8是一个不降序数列（有相等的升序），也就是逐渐变多，而8，5，4，3是一个不升序数列（有相等的降序），逐渐减少。8正好是升序数列的最后一个，也是降序数列的第一个。
其他几组也是同样的道理。

那么这样就好办了！我们只需要找到第一个升序数列的末尾并取出它就可以算成功完成了“局部的最优解”，再通过这个继续取出更多的数，直到取出s个数来，从局部的最优解进阶到全局的最优解，这一道题就完成了！

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>

using namespace std;
typedef long long ll;
const int MOD = 10000007;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 300;

int main()
{
	string n;
	int s;
	cin>>n>>s;
	while(s--)
	{
		int len = n.length();
		for(int i=0; i<len; i++)
		{	//删除遇到的第一个递减序列的第一个数字(若整个字符串为非递减序列，则删去末尾的数字)
			if(n[i]>n[i+1]||i==len-1)
			{
				n.erase(i, 1); //把当前字符从字符串中删除(删除从i位置开始的1个字符)
				break;
			}
		}
	}
	while(n[0]=='0'&&n[1]) //去掉前缀0，并至少保留1个数字
		n.erase(0,1); //删去当前字符串开头的'0'
	cout<<n;
	return 0;
}