4906 删数问题（另一种贪心思路）

4906 删数问题

时间限制: 1 s

空间限制: 2000 KB

题目等级 : 黄金 Gold

题目描述 Description

键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N 和S，寻找一种方案使得剩下的数字组成的新数最小。

输入数据均不需要判错。

输出组成的新的正整数。（N不超过240位）

输入描述 Input Description

第一行，输入一正整数N（N<=10^240），表示要删的数；

第二行，输入一正整数S，表示删去的个数，当然S小于N的位数。

输出描述 Output Description

仅一行，输出删数后形成的最小数。

样例输入 Sample Input

【1】

5768

【2】

8796542

样例输出 Sample Output

【1】

568

【2】

542

数据范围及提示 Data Size & Hint

1<=N<=10240

1<=S<=239

注意开头的0应略去！！[要小心]

思路：要求去掉s位，也就是在总长度len中去掉s个数，那么也就是保留(len-s)位数；

设 x=len-s; 保留x位数。

可以从第一位找，到（后面还有 x-1 位时停止，也就是使后面只剩下（x-1）位）；在这里面找到最小的数，算是第一个数；

然后以这个数的下一个为起点，到（后面有x-2位时停止），也是找最小的。以此类推，找出全部的数。

1. 那为什么找到后面有x-1 位？

举个例子：

789456123 5

从 789456123 去掉5位，即保留4位数字，x=4;

从这里面挑 4 个数，使这个数最小;那选要谁呢？

先选最高位，最高位小的当然要小，所以选最小的做最高位；

那么因为最高位只能是 789456 这6个数中的一个，为什么？因为最高位最差只能是6，不能是1 2 3，还要剩下三个数做百位，十位，个位；

所以只能从1到后面有3位（这不就是x-1吗!!!）时停止，在包括的数中挑选最小的；

选百位，十位，个位时同理。

2.代码中16行是：end=n+1

解释一下：以这个为例，len = 9 , s = 5 , 保留的数 x = len - s = 9 - 5 = 4 ;

到后面还有 x-1 位，那前面有 len - (x-1) 位（因为总长len）,

x = len - s ;len-(x - 1)=len-(len-s-1)=len-len +s +1=s+1;

也就是从1到 s+1位中找最小的。

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 int num[300];
 5 string s;
 6 int len,n;        //len 长度 
 7 int ans=10,beg,end,can,p;
 8 bool flag=0;
 9 int main()
10 {
11     cin>>s>>n;
12     for(int i=0;i<s.size();++i)
13         num[i+1]=s[i]-48;        //记录下数字 
14     len=s.size();
15     beg=1;        //起始位置 
16     end=n+1;    //终止位置 
17     while(end<=len)    
18     {
19         ans=10;        //设置成最大 
20         for(int i=beg;i<=end;++i)  //找出最小的一位数 
21         {
22             if(num[i]<ans)
23             {
24                 ans=num[i];
25                 can=i;
26             }
27         }
28         if(ans)  //判断0的情况 
29         {
30             cout<<ans;
31             flag=1;            
32         }
33         else if(!ans&&flag)cout<<ans;
34         beg=can+1;
35         end++;
36     }
37     if(!flag)cout<<0;
38     return 0;
39 }