【算法】删数问题（贪心算法）

有一个长度为n（n <= 240）的正整数，从中取出k（k < n）个数，使剩余的数保持原来的次序不变，求这个正整数经过删数之后最小是多少。

输入格式: n和k

输出格式: 一个数字，表示这个正整数经过删数之后的最小值。

输入样例:

178543 4

输出样例:

13

问题分析 在这里要知道两个函数 1。erase函数： （1）erase(pos,n); 删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符 （2）erase(position);删除position处的一个字符(position是个string类型的迭代器) （3）erase(first,last);删除从first到last之间的字符（first和last都是迭代器）

2。substr函数： 假设：string s = “0123456789”; （1）string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾：sub1 = “56789”

（2）string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位：sub2 = “567”

两个相邻的数比较，如果前一个数比后一个数大，就删掉，计数器加1，循环直到计数器等于要删除的个数，最后输出字符串。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
          
   
    string n;
    int k;
    cin>>n>>k;
    int i=-1,num=0;
    int len;
    while(num<k){
          
   
        len=n.length();
        i++;
        if(n[i]>n[i+1]){
          
   
            n.erase(i,1);
            num++;
            i=-1;//表示从头开始检查
        }
    }
    i=0;
    cout<<n.substr(i,len)<<endl;
}