网易2018——删除数字

删除数字（C++）

时间限制：C/C++语言1000MS；其他语言3000MS

内存限制：C/C++语言65536KB；其他语言589824KB

题目描述：
给出一个字符串A，表示一个N位正整数，删除其中k位数字，使得剩余的数字仍然按照原来的顺序排列产生一个新的正整数。找到删除k个数字之后的最小正整数。N<=240，K<=N。

输入：

输入包含多组测试数据，每组数据为一行，每一行数据包含两个值，第一个值为A，第二个值为k，两个值中间有一个空格。
输出：
输出计算出的最小正整数
样例输入
987132 4

1000230 5

样例输出
12

解题思路：

误区：

　　并不是删除最大的数字，而是按高位依次删除大的数

 1 #include <iostream>
 2 #include <sstream>
 3 #include <string>
 4 #include <vector>
 5 using namespace std;
 6 
 7 
 8 int main()
 9 {
10     int A;
11     int k;
12     string str;
13     vector<int>res;
14     stringstream ss;
15     for(int t = 0;t<1;++t)//输入数据大小
16     {
17         cin >> A >> k;        
18         ss << A;
19         ss >> str;    //转换为字符串更方便
20         if (k >= str.size())//删除的位数超过输入数字的位数
21         {
22             A = 0;
23             res.push_back(A);
24             continue;
25         }        
26         while (k--)
27         {
28             int flag = 1;//数组是否为递增标记
29             for (int i = 1; i < str.size(); ++i)
30                 if (str[i-1] > str[i])//删除较大的数字
31                 {
32                     str.erase(i-1,1);
33                     flag = 0;
34                     break;
35                 }
36             if (flag)//剩下的为递增，直接删除后面的数字就行
37             {
38                 str.assign(str, 0, str.size() - k-1);
39                 break;
40             }
41         }
42         ss.str("");
43         ss.clear();
44         ss << str;
45         ss >> A;//将字符转换为数字
46         res.push_back(A);
47         ss.str("");
48         ss.clear();
49         
50     }
51     for (auto a : res)
52         cout << a << endl;
53     system("pause");
54     return 0;
55 }