问题 D: 删数问题

题目描述

输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。
输出新的正整数。（N不超过240位）输入数据均不需判错。

输入

n
s

输出

最后剩下的最小数。

样例输入

175438
4

样例输出

13

问题分析

从左到右遍历数字，移除那些会使得剩余的数字尽可能小的数字，直到我们移除了 S 个数字。

这个算法的关键在于识别何时移除一个数字。一般而言，如果一个数字大于其右边的数字，移除它会使得结果更小。我们重复这个过程，直到移除了 S 个数字或者没有更多的这样的数字可移除为止。

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

int main() {
    string n;
    cin >> n; // 读取数字字符串
    int s;
    cin >> s; // 读取要移除的数字数量

    string ans = ""; // 初始化结果字符串
    for (char c : n) { // 遍历输入的数字字符串
        // 如果还需要移除数字，并且结果字符串不为空，
        // 且结果字符串的最后一个字符大于当前遍历的字符
        while (s > 0 && !ans.empty() && ans.back() > c) {
            ans.pop_back(); // 移除结果字符串的最后一个字符
            s = s - 1; // 减少剩余要移除的数字数量
        }
        // 如果当前字符不是'0'，或者结果字符串不为空（即不会导致前导零）
        if (c != '0' || !ans.empty()) {
            ans.push_back(c); // 将当前字符添加到结果字符串
        }
    }
    // 如果在移除过程结束后仍然需要移除更多数字
    while (s > 0 && !ans.empty()) {
        ans.pop_back(); // 继续从结果字符串的末尾移除字符
        s = s - 1; // 减少剩余要移除的数字数量
    }
    // 如果结果字符串为空，则输出'0'，否则输出结果字符串
    cout << (ans.empty() ? "0" : ans);
}