题目描述

键盘输入一个高精度的正整数 n（不超过 250 位），去掉其中任意 k 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 n 和 k，寻找一种方案使得剩下的数字组成的新数最小。

输入格式

输入两行正整数。

第一行输入一个高精度的正整数 n。

第二行输入一个正整数 k，表示需要删除的数字个数。

输出格式

输出一个整数，最后剩下的最小数。

输入输出样例

输入 #1复制

175438 
4

输出 #1复制

13

说明/提示

用 len(n) 表示 n 的位数，保证 1≤k<len(n)≤250。

解题思路

乍一看挺简单，实现起来有点小复杂。

• 注意题目要求去掉k个数字后剩下的数字要按原来的左右次序输出，即保持相对位置不变。
• 那我们就不能只挑选最大的k个数字去掉，比如1400562，需要去掉两个数字，那么我们选择去掉最大的两个数字后，应该输出14002，显然不是最优解，因为我们可以选择去掉1,4，输出00562（输出时不需要前导0），而562<14002。显然此路走不通，需要另辟蹊径。
• 把去掉k个数字转换为选择n-k个数字。由于我们需要保持输出的数字之间的相对位置不变，那么每一个数字的选择都是有范围的（比如1400562，去掉两个数，那么需要选择5个数，第一个数只能在前三位“140”中选择，确保后面至少留下4个数，确保最终能选择到5个数。同样，第二个数只能在“0”中选，确保后面至少留下3个空位，且确保第二个数字要在第一个数字（按照规则应该选第一个0）后面，以此类推）
• 每一个数字都在其选择范围内选择最小的第一个数（当有多个相同的最小值时），这样做的目的是尽可能给后续的数字的选择更大的选择空间，即每一步都尽可能使后续的数字能选到最小的数（贪心）。
• 根据每个数的选择范围，每次截取出一个子串，找出其中最小值的下标，计算他在原来的串中的位置（该步不可省，因为需要据此选择下一个截取子串的范围），并将相应值添加到结果串中。
• 输出：前导0不输出，但如果结果为0需要输出一个0。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
	string s;
	cin >> s;
	int k;
	cin >> k;
	int n = s.size();
	//需要删除k个数字，说明需要选择n-k个数字
	int st = -1;
	string ss = "";
	for (int i = 1; i <= n - k; i++) {
		string sy = s.substr(st + 1, k + i - st - 1);
		//int st = min_element(sy.begin(), sy.end()) - sy.begin() + st + 1;
		auto ee = min_element(sy.begin(), sy.end());
		int rr = ee - sy.begin();
		st = rr + st + 1;
		ss += s[st];
	}
	int flag = 0; //表示还没有进行输出
	for (int i = 0; i < ss.size(); i++) {
		if (stoi(ss) == 0) {
			cout << 0;
			break;
		}
		if (ss[i] == '0') {
			if (!flag) {
			} else {
				cout << ss[i];
				flag = 1;
			}
		} else {
			cout << ss[i];
			flag = 1;
		}

	}
	//cout << ss;
	return 0;
}