练85.3 删数问题(Noip1994)

解题思路

维护单调不降数字栈。读新数字c时，只要可删且栈顶>c就弹出栈顶并减删除次数，再压入c。全部读完若仍需删，就从末尾删；最后去掉前导0。

正确性说明

最小数字优先让高位尽量小，若相邻保留候选前大后小，删除前者能严格减小更高位；栈反复完成这种有益删除。若剩余单调不降，删末尾最不影响较小高位。

易错点

保留原左右顺序；若全删或只剩0，输出0。

复杂度

位数D，时间O(D)，空间O(D)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string n;
    int s;
    cin >> n >> s;
    string st;
    for (char c : n) {
        while (s > 0 && !st.empty() && st.back() > c) {
            st.pop_back();
            s--;
        }
        st += c;
    }
    while (s > 0 && !st.empty()) {
        st.pop_back();
        s--;
    }
    size_t p = st.find_first_not_of('0');
    cout << (p == string::npos ? "0" : st.substr(p)) << "\n";
    return 0;
}