问题 D: 删数问题

2024-01-07 17:34:17

题目描述

输入一个高精度的正整数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);
}

文章来源:https://blog.csdn.net/lcc1737/article/details/135424650
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。