M04137:最小新整数

monotonous-stack, dfs, http://cs101.openjudge.cn/practice/04137/

给定一个十进制正整数n(0 < n < 1000000000)，每个数位上数字均不为0。n的位数为m。现在从m位中删除k位(0<k < m)，求生成的新整数最小为多少？例如: n = 9128456, k = 2, 则生成的新整数最小为12456

输入

第一行t, 表示有t组数据；接下来t行，每一行表示一组测试数据，每组测试数据包含两个数字n, k。

输出

t行，每行一个数字，表示从n中删除k位后得到的最小整数。

样例输入

2
9128456 2
1444 3

样例输出

12456
1

这个问题是典型的贪心算法应用，可以通过单调栈（Monotonous Stack）来高效解决。

解题思路

贪心策略：要使剩下的数字最小，我们需要让较小的数字尽量排在最高位（左侧）。当我们从左向右遍历数字时，如果发现当前数字比前一个数字小，那么删除前一个数字（高位较大的数）一定会使结果更小。
具体算法：
- 维护一个栈，遍历数字字符串的每一位。
- 如果当前数字比栈顶数字小，且我们还有剩余的删除次数 $k$ ，则弹出栈顶数字，并将 $k$ 减 1。重复此过程直到栈为空、当前数字不小于栈顶或 $k$ 为 0。
- 将当前数字压入栈中。
- 处理剩余的 $k$ ：如果遍历结束后 $k$ 仍然大于 0（说明原数字序列是单调递增的，如 12345），则从栈的末尾删除剩下的 $k$ 个元素。
- 最后处理：将栈中的数字拼接成字符串输出。题目规定数字不含 0，所以不需要考虑前导零的问题。

何为单调栈？顾名思义，单调栈即满足单调性的栈结构。例如：维护一个整数的单调递增栈。

python

# 23n2300012276(管骏杰）
def removeKDigits(num, k):
    stack = []
    for digit in num:
        while k and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    while k:
        stack.pop()
        k -= 1
    return int(''.join(stack))
t = int(input())
results = []
for _ in range(t):
    n, k = input().split()
    results.append(removeKDigits(n, int(k)))
for result in results:
    print(result)

【金于珑工学院】思路：直接递归实现，思路很清晰。如果要删除k个数，就检查前k+1个数，找到其中最小的那一个数，在它之前的全部数都删除，在它之后的数继续进行操作即可，然后处理一下边界条件。

python

import sys
def solve():
    data = iter(sys.stdin.readlines())
    t = int(next(data))
    ans = []
    def remove(num,cnt):
        if cnt == 0:
            return num
        if cnt == len(num):
            return ''
        min_num = 9
        pointer = 0
        for index in range(cnt+1):
            if int(num[index])  < min_num:
                min_num = int(num[index])
                pointer = index
        return num[pointer] + remove(num[pointer+1:],cnt - pointer)
    for i in range(t):
        n,k = next(data).split()
        ans.append(remove(n,int(k)))
    for i in ans:
        print(i)


solve()

M04137:最小新整数 ​

M04137:最小新整数