贪心3--删数问题

一、心得

 

二、题目及分析

 

题目：

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

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

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

Simple Input

 178543

 4

Simple Output

 13

 

思路：

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

三、代码及结果

 

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 int main(){ 5     string s; 6     cin>>s; 7     int n; 8     cin>>n; 9     int len=s.length();10     int a[300];11     for(int i=0;i
       
        a[j+1]){17                 for(int k=j;k