删除字符问题（贪心）

 1 /*
 2 键盘输入一个高精度的正整数ｎ（<=240位），去掉任意ｓ个数字后剩下的数字按原左右次序将组成一个新的正整数。
 3 编程对给定的ｎ和ｓ，寻找一种方案，使得剩下的数最小。
 4 Simple Input
 5      178543
 6      4
 7 Simple Output
 8  13
 9  */
10 #include <iostream>
11 #include <string>
12 using namespace std;
13 string s;
14 int num;
15 void fun()
16 {
17     int i,j,k,t;
18     int size = s.length();
19     for(i=0;(s.length()+num)>size;)
20     {//必须是i<s.length(),不是i<s.length()-1,否则456123 3会输,123而不是12， 因为最后的3会因i<s.length()-1而直接结束，不在进行if比较    
21     //正确结果应该是以第(s.length()+num)==size结束 
22     //所以i<s.length()条件可以不要 
23         if(s[i]>s[i+1])
24         {
25             s.erase(i,1);
26             i = 0;
27             continue;
28         }
29         else
30             i++;//不能放在for内，因为 
31     }
32     cout<<s<<endl;
33 }
34     
35 int main()
36 {
37     int i,j,k,t;
38     while(cin>>s>>num)
39     {
40         fun();
41         s.clear();
42     }
43     return 0;
44 }
45 //注意：每次删除最大的数字是不对的，该题的贪心策略是删除一个数字后剩下的数是删除其他数字中最小的，
46 //如：178456129 3，正确结果是145129,错误结果是145612

刚才同学说：申请一个栈从左往右扫描，如果新入栈元素小于栈顶元素则弹栈并计数cnt（删除的字符个数），如果最后cnt<num,则继续弹栈num-cnt次，最后需要借助另一个栈逆序输出，cnt == num时并输出没入栈的剩余数字；不可用双端队列或者队列（因为双端队列只不过是可在对头插入，并不能在队尾删除），或者直接使用数组模拟栈，最后从前往后输出剩余的元素。