【例6.3】删数问题(Noip1994)

题目描述

输入一个高精度正整数 $n$ （不超过 240 位，首位不为 0），去掉其中任意 $s$ （$s < $ 位数）个数字后，剩下的数字按原左右次序组成一个新的正整数。编程寻找一种方案使新数最小，输出这个最小数。输入数据均不需判错。

输入两行：第一行为 $n$ ，第二行为 $s$ 。

输出最后剩下的最小数（若剩下的数字全是 0，输出 0）。

input

1
2175438
4

output

思路

剩下的位数固定为 $L-s$ ，比较数值就是比较字典序；贪心规则是：从左往右遇到第一个下降位 $a_i > a_{i+1}$ 就删掉 $a_i$ ，串已单调不减时删末位。用一个单调不减栈一次扫描实现：读入新数字时只要栈顶比它大且还有删除名额就弹出栈顶，扫描结束后名额没用完就从栈尾继续删，最后剥掉前导零输出，总时间 $O(L)$ 。

参考代码

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#!/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 05:05
# update_at: 2026-09-30 05:08

import sys


def smallest_after_deletions(digits: str, s: int) -> str:
    """在 digits 中删去 s 位，返回剩下数字串能组成的正整数（去掉前导零）。

    维护一个单调不减的栈：新来的一位如果比栈顶小，就说明"栈顶那位靠左却更大"，
    删掉它一定比删掉当前位更划算，于是反复弹栈；扫完还有删除余量时，
    栈已经不减，剩下的名额只能从末尾花掉。
    """
    kept: list[str] = []
    budget = s  # 还剩几个删除名额
    for digit in digits:
        while budget and kept and kept[-1] > digit:  # 左侧更大且更靠前，删它
            kept.pop()
            budget -= 1
        kept.append(digit)
    if budget:  # kept 此时单调不减，末尾几位最大，删它们最划算
        del kept[len(kept) - budget:]
    return ''.join(kept).lstrip('0') or '0'  # 全 0（或精光）时题面要求输出 0


def solve() -> None:
    data = iter(sys.stdin.read().split())
    n = next(data)
    s = int(next(data))
    print(smallest_after_deletions(n, s))


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
52
53
54/**
 * 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 09:42
 * update_at: 2026-10-05 09:42
 */

#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXL = 250; // n 不超过 240 位

char num[MAXL]; // 输入的数字串
char stk[MAXL]; // 单调不减栈：stk[0..top-1] 是当前确定保留的前缀
ll top;         // 栈顶指针（栈内元素个数）
ll s;           // 还能删多少个数字（删除名额）

int main() {
    scanf("%s", num);
    scanf("%lld", &s);

    ll len = strlen(num);

    // 贪心：读入新数字 c 时，栈顶比 c 大说明栈顶那位靠左却更大，
    // 删掉它一定更优，弹出并消耗一个删除名额，直到栈顶不大于 c 或名额用完
    top = 0;
    for (ll i = 0; i < len; i++) {
        char c = num[i];
        while (s > 0 && top > 0 && stk[top - 1] > c) {
            top--; // 弹出栈顶 = 删掉一个数字
            s--;
        }
        stk[top] = c;
        top++;
    }

    // 扫描结束后串已单调不减，名额没用完就从末尾（最大的几位）继续删
    top -= s;
    s = 0;

    // 剥掉前导零；剩下的字符全是 0 时输出 0
    ll start = 0;
    while (start < top - 1 && stk[start] == '0')
        start++;

    for (ll i = start; i < top; i++)
        putchar(stk[i]);
    putchar('\n');

    return 0;
}

【例6.3】删数问题(Noip1994)

目录

题目描述

思路

参考代码