题目链接
题目描述
键盘输入一个高精度的正整数 $N$（不超过 $250$ 位），去掉其中任意 $k$ 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 $N$ 和 $k$，寻找一种方案使得剩下的数字组成的新数最小。
输入格式
$n$（高精度的正整数 )。
$k$（需要删除的数字个数 )。
输出格式
最后剩下的最小数。
题解
首先，直接贪心删去最小的是错的，可以举出反例 $N = 1329, k = 1$ 时答案应该是 $129$ 而不是 $132$。
考虑去维护一个单调不减栈，每次入栈的时候进行判断，依次删去 $k$ 个不满足不减的元素，可以保证最后一定是最小
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #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;
}
|
注意
- 注意到第 11 行
k && sta.size() && sta.top() > 0 && s[i] - '0' < sta.top() 中 sta.size() 和 sta.top() 不能反过来，否则 RE
