删数问题（NOI94）

删数问题（NOI94）

输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序

组成一个新的正整数。

编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。

输出新的正整数。（N不超过240位）输入数据均不需判错。

【输入】

n

s

【输出】

最后剩下的最小数。

【样例输入】

175438

4

【样例输出】

13

分析：

由于正整数n的有效数位为240位，所以很自然地采用字符串类型存贮n。

那么如何决定哪s位被删除呢？是不是最大的s个数字呢？显然不是，大家很容易举出一些反例。

为了尽可能逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，

即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则删除第一个递减区间的首字符，

这样删一位便形成了一个新数字串。然后回到串首，按上述规则再删下一个数字。重复以上过程s次为止，

剩下的数字串便是问题的解了。