主要内容 #

1. 问题描述
2. 算法思路
3. 参考程序

1. 问题描述 #

给定n位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个新 的正整数。对于给定的n位正整数a和正整数 k，设计一个算法找出剩下数字组成的新数最 小的删数方案。
输入格式
第 1 行是1 个正整数 a。第 2 行是正整数k。
输出格式
输出最小数。
输入样例
175438
4
输出样例
13

2. 算法思路 #

我们的贪心策略是使得剩下的数尽量的小，因此我们要保留的数字应该是前面一位数应该比后面的数小，然后根据贪心算法步骤逐步进行。

• 把求解的问题分成若干个子问题；
• 对每一子问题求解，得到子问题的局部最优解；
• 把子问题的解局部最优解合成原来解问题的一个解。

把问题分成求解前一个数和后一个数的大小问题，每一步都要求是最小的值，然后去掉大的那个值，当剩下的数是升序时，我们应该从最后的数开始删（因为最后那个数最大）。

3. 参考程序 #

#include <iostream>
using namespace std;

int main() {
        string a;
        int k;
        cin>>a>>k;
        int len=a.size(); 
        while(k--)
            for(int i=0;i<len;i++) 
                if(a[i]>a[i+1]||i==len-1)
                {
                    a.erase(i,1); //抹去数组下标为i的一个数
                    break; 
                }
       while(a[0]=='0'&&a[1]>0) //当前面的数是0时或者防止数全部为0是数组为null的情况
            a.erase(0,1); 
       cout<<a<<endl; 
    return 0;
}