算法设计与分析 | 删数问题

题目描述

给定n位正整数a，去掉其中任意k个数字后，剩下的数字按原次序排列成一个新的正整数。 
n (1<=n<=200)位的正整数a和k，k小于n。

输入

可输入多组测试数据，每组测试数据分两行，每行一个数，数的含义如下。 
第一行：正整数a（a是大于0的一个n位正整数） 
第二行：正整数k 
以0来结束测试数据。

输出

输出每组测试数据所得出的删k位数之后的最小数。 
若输出的数首位是0，无须理会，0也直接输出即可。例如：024，就直接输出024，无须改成24。

样例输入?

178543
4
87654321
2
123456789
1
254193
1
90249
2
0

样例输出?

13
654321
12345678
24193
024

分析：

其实删数问题就是比较输入的每一位数字的大小，然后把位置在前面的并且数字比后面一位数字大的先删除，其中使用的是c++里面的erase()函数进行删除：

erase(pos,n); 删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符

定义了flag来及时结束循环，

string result = s.erase(len - c, s.size() - len + c);

上面这个代码是来解决：如果前面的数字都比后面一位的数字都要小的情况下，然后要删除后面的数字，就可以获得最小数。

代码：

#include <iostream>
#include <string>
using namespace std;
//删数问题
string delete_num(string s, int sz) {
	int len = s.size();
	int c = sz;
	while (sz--) {
		bool flag = false;
		for (int i = 0; i < len; i++) {
			if (s[i] > s[i + 1]) {
				s.erase(i,1);
				flag = true;
				break;
			}
		}
		if (flag == false) break;


	}
	string result = s.erase(len - c, s.size() - len + c);
	return result;

}

int main() {
	string str;  
	int s;   
	while (true)
	{
		cin >> str;
		if (str == "0")
		{
			break;
		}
		cin >> s;
		cout << delete_num(str, s) << endl;   

	}
	
}