贪心算法实验报告-删数问题

给定n位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数 k，设计一个算法找出剩下数字组成的新数最小的删数方案。如果数字最前面有0不输出。

输入格式:

第 1 行是1 个正整数 a。第 2 行是正整数k。

输出格式:

输出最小数。

输入样例:

在这里给出一组输入。例如：

178543 
4 （结尾无空行）

5001 
1(结尾无空行)

123456 
2(结尾无空行)

109 
1 (结尾无空行)

输出样例:

在这里给出相应的输出。例如：

13(结尾无空行)

1(结尾无空行)

1234(结尾无空行)

9(结尾无空行)

#include
#include
#include
using namespace std;

int main(){
    int n, i, j, k;
    string a;
    
    cin>>a>>n;
    int len=a.size();
     
    //删数过程（删掉k个数） 
    for(k=0; k){
        for(i=0; i1; i++){
            //从最高位开始比较，若a[i] > a[i+1]（高位比地位的数字更大），该位后面所有位往前挪一位（删掉a[i]）
            if(a[i] > a[i+1]){
                for(j=i; j1; j++)
                    a[j] = a[j+1];
                break;  
            }
        }
        //删掉一位后len--
        len--; 
    }

    i = 0;
    //删数最后的数以0开头
    while(i <= len-1 && a[i] == '0')i++;

    //若全为0的情况
    if(i == len)
        cout<<"0"<<endl;
    //从第一个非0开始输出
    else
        for(j=i; j<=len-1; j++)
            cout<<a[j];
    
    return 0;
}

删数过程中有两个for循环，if里面又套了一个for循环，故时间复杂度是O（n*n*n）