最小新整数

题目描述

给定一个十进制正整数 $n$ （每位数字均不为 $0$ ），其位数为 $m$ 。现从 $m$ 位中删去恰好 $k$ 位（ $0<k<m$ ），要求保留下来的位保持原有先后顺序，问能得到的最小新整数。

输入第一行 $t$ ，接下来 $t$ 行每行两个数 $n,k$ 。输出 $t$ 行，每行一个整数。由于各位均不为 $0$ ，结果的字典序就是数值大小。样例： $n=9128456,k=2$ 得 $12456$ ； $n=1444,k=3$ 得 $1$ 。

思路

删 $k$ 位等于留 $L=m-k$ 位，逐位从左往右贪。维护单调非降栈扫原串：遇到当前数位 $d$ 时，若栈顶 $x>d$ 且还有删除额度就弹掉 $x$ （相当于把 $d$ 提到 $x$ 占过的输出位上），弹不动再压栈；扫完若还剩额度，说明栈已非降，直接砍掉末尾若干位即可。每个数位最多进出栈一次，整体 $O(m)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 00:43
# update_at: 2026-09-30 00:51

import sys
from collections.abc import Iterable


def smallest_after_deleting(digits: str, k: int) -> str:
    """删掉 digits 中的 k 位（保持原有顺序），返回能得到的最小数字串。

    单调栈：按输出位从左往右定，每位取当前窗口里最靠左的最小值。扫到 digit 时，
    栈顶比它大就说明栈顶占着的槽位应该让给它（把更小的数位提到前面只会更小），
    弹出栈顶即花掉一次删除额度；弹不动了再压栈，于是栈内始终非降。
    每个数位最多进出栈各一次。
    """
    stack: list[str] = []
    for digit in digits:
        while k and stack and stack[-1] > digit:  # 严格大于：相等时保留更靠左的那位
            stack.pop()
            k -= 1
        stack.append(digit)
    return ''.join(stack[:len(stack) - k])  # 额度没用完说明栈已非降，剩余删除只能砍末尾


def solve() -> None:
    """逐组读入 n 与 k，输出删除 k 位后最小的新整数。"""
    data: Iterable[bytes] = iter(sys.stdin.buffer.read().split())
    cases = int(next(data))
    out: list[str] = []
    for _ in range(cases):
        digits, k = next(data).decode(), int(next(data))  # n 保持字符串，转 int 会丢位数
        out.append(smallest_after_deleting(digits, k))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 06:04
 * update_at: 2026-10-05 06:04
 */
//
// main.cpp：删 k 位求最小新整数。
// 解法：单调栈一次遍历，每个数位最多进出栈各一次，整体 O(m)。
// 与 main.py 同算法，方便 C++ 学习者对照。
//

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

typedef long long ll;

const int MAXM = 20;          // m < 10，位串不会超过 9，留点余量

char n_buf[MAXM];             // 输入的整数串，按字符存放，避免 int 丢位数
char stk[MAXM];               // 单调非降栈：栈内保存当前选定的输出位
int top;                      // 表示每层数位的栈顶下标（stk 表示已选位）

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int k;
        scanf("%s %d", n_buf, &k);

        top = 0;              // 每组重新建栈，top=0 表示空栈
        // 一次扫描：栈顶 > 当前数位 且 还有删除额度，就弹栈顶
        for (int i = 0; n_buf[i]; ++i) {
            char d = n_buf[i];
            while (k > 0 && top > 0 && stk[top - 1] > d) {
                --top;        // 弹栈顶，花掉一次额度
                --k;
            }
            stk[top++] = d;   // 弹不动再压栈；压栈后栈仍非降
        }

        // 若扫描结束还剩额度，说明栈内已经非降，剩余删除全部砍在末尾
        int keep = top - k;
        for (int i = 0; i < keep; ++i) {
            putchar(stk[i]);
        }
        putchar('\n');
    }
    return 0;
}

目录

题目描述

思路

参考代码