最小数 - 高精度整数数字删除算法

题目描述

输入一个高精度的正整数 n 和一个正整数 s，从 n 中任意删去 s 个数字，剩下的数字按与按顺序排列可以得到一个新的正整数 t。给出 n 和 s，寻找一种方案使得删完剩下的数字组成的新正整数 t 最小，输出这个最小的 t。

输入格式

从标准输入读入数据。第一行输入一个高精度的正整数 n（不含前导 0，最多 1,000 位）。第二行输入一个正整数 s（s 严格小于 n 的位数）。

输出格式

输出到标准输出。输出最小的 t（不含前导 0）。

样例 #1

样例输入 #1

121389789
3

样例输出 #1

样例 #2

样例输入 #2

121389989
3

样例输出 #2

算法思路

本题的核心思想是使用单调栈来维护一个递增的数字序列。

初始化单调栈: 初始化一个单调栈 stk，并将栈顶元素设置为 -1，方便后续比较。
遍历数字: 逐位遍历输入的数字 n。
判断是否入栈: 对于当前遍历到的数字 n[i]，如果栈顶元素大于 n[i] 且当前栈中剩余元素数量加上剩余待遍历数字数量大于 len - s（即最终要保留的数字数量），则弹出栈顶元素。这样可以保证栈中始终保持递增序列，并且最终保留的数字数量不会超过 len - s。
入栈: 如果满足入栈条件，将当前数字 n[i] 入栈。
输出: 遍历完成之后，从栈顶开始输出栈中元素，即为最终的最小数字 t。

C++ 代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

char n[N];
int s;
int stk[N], tt;

int main()
{
    cin >> n >> s;
    int len = strlen(n);
    stk[0] = -1;
    for (int i = 0; i < len; i ++ )
    {
        while (tt && stk[tt] > n[i] && tt + len - i > len - s) tt -- ;
        if (tt < s) stk[ ++ tt] = n[i];
    }
    for (int i = 1; i <= tt; i ++ ) cout << stk[i];
    cout << endl;
    return 0;
}

代码解析

#include <iostream>: 包含输入输出流库。
#include <cstring>: 包含字符串操作库。
#include <algorithm>: 包含算法库。
using namespace std;: 使用 std 命名空间。
const int N = 1010;: 定义常量 N 为数组大小。
char n[N];: 定义字符数组 n 用于存储输入的高精度整数。
int s;: 定义整型变量 s 用于存储要删除的数字数量。
int stk[N], tt;: 定义整型数组 stk 作为单调栈，tt 为栈顶指针。
int main(): 主函数入口。
cin >> n >> s;: 从标准输入读取高精度整数 n 和删除数字数量 s。
int len = strlen(n);: 获取高精度整数 n 的长度。
stk[0] = -1;: 初始化单调栈，栈顶元素设置为 -1。
for (int i = 0; i < len; i ++ ): 遍历数字 n。
while (tt && stk[tt] > n[i] && tt + len - i > len - s) tt -- ;: 判断是否需要弹出栈顶元素。
if (tt < s) stk[ ++ tt] = n[i];: 如果满足入栈条件，将当前数字 n[i] 入栈。
for (int i = 1; i <= tt; i ++ ) cout << stk[i];: 输出栈中元素，即为最终的最小数字 t。
cout << endl;: 换行。
return 0;: 返回 0，表示程序执行成功。

总结

本题通过使用单调栈算法，有效地解决了从高精度整数中删除指定数量的数字以得到最小新整数的问题。该算法简单易懂，时间复杂度为 O(n)，空间复杂度为 O(n)，适用于处理这类高精度整数数字删除问题。