贪心3--删数问题

贪心3--删数问题

一、心得

 

二、题目及分析

 

题目：

键盘输入一个高精度的正整数ｎ（<=240位），

去掉任意ｓ个数字后剩下的数字按原左右次序将组成一个新的正整数。

编程对给定的ｎ和ｓ，寻找一种方案，使得剩下的数最小。

Simple Input

 178543

 4

Simple Output

 13

 

思路：

每一步总是选择一个使剩下的数最小的数字删除，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则删除第一个递减区间的首字符，这样删一位便形成了一个新的数字串。然后回到串首，按上述规则再删除下一个数字

三、代码及结果

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    cin>>s;
    int n;
    cin>>n;
    int len=s.length();
    int a[300];
    for(int i=0;i<len;i++){
        a[i+1]=s[i]-'0';
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<len;j++){
            if(a[j]>a[j+1]){
                for(int k=j;k<len;k++){
                    a[k]=a[k+1];
                }
                break;
            }
        }
        len--;
    }
    for(int i=1;i<=len;i++){
        cout<<a[i];
    }
    cout<<endl;
    return 0;
}