题目链接

题目描述

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

输入格式

$n$（高精度的正整数 )。

$k$（需要删除的数字个数 )。

输出格式

最后剩下的最小数。

题解

首先，直接贪心删去最小的是错的，可以举出反例 $N = 1329, k = 1$ 时答案应该是 $129$ 而不是 $132$。

考虑去维护一个单调不减栈，每次入栈的时候进行判断，依次删去 $k$ 个不满足不减的元素，可以保证最后一定是最小

代码

cpp

#include <bits/stdc++.h>
using namespace std;
stack<int> sta;
char s[255];
int k, idx;
int ans[255];
int main() {
    scanf("%s %d", s + 1, &k);
    int len = strlen(s + 1);
    for (int i = 1; i <= len; i++) {
        while ( k && sta.size() && sta.top() > 0 && s[i] - '0' < sta.top() ) sta.pop(), k--;
        sta.push(s[i] - '0');
    }
    while (k-- && sta.size()) sta.pop();
	while (!sta.empty()) {
		ans[++idx] = sta.top();sta.pop();
	}
	while(ans[idx] == 0 && idx) --idx;
	if(idx == 0) puts("0");
	else for(int i=idx;i>=1;i--) printf("%d",ans[i]);
    return 0;
}

注意

1. 注意到第 11 行 k && sta.size() && sta.top() > 0 && s[i] - '0' < sta.top() 中 sta.size() 和 sta.top() 不能反过来，否则 RE