删数字

1 题目描述

题目：luogu P1106: 删数问题。

给定一个不超过 $250$ 位的正整数 $n$，删除其中恰好 $k$ 个数字，剩下的数字保持原来的左右顺序，组成一个新的非负整数。

求能够得到的最小整数。

输入格式

第一行输入正整数 $n$。

第二行输入整数 $k$，表示需要删除的数字个数。

输出格式

输出删除后能够得到的最小整数，不输出前导零。如果剩下的数字全是零，输出 0。

数据范围

$1\le k<\operatorname{len}(n)\le250$，其中 $\operatorname{len}(n)$ 表示 $n$ 的位数。

输入样例：

1
2

175438
4

输出样例：

1

13

2 解析

如果只删除一个数字，应该删哪一位？

先看一个简单的例子：175438。删除 1 会让开头变成 7，显然不好；删除 7 后得到 15438，开头的第二位由 7 变成了 5，数字就变小了。

因为删除后的位数相同，比较大小时，从左往右第一个不同的数字越小，整个数就越小。所以我们应优先改善靠左的位置，而不是简单地删除最大的数字。

设当前数字序列为 $a_1,a_2,\ldots,a_m$。找到第一个满足

的位置 $p$，删除 $a_p$。这样原来的 $a_{p+1}$ 就会前移，在这个位置放上一个更小的数字。

如果不存在这样的 $p$，说明整个序列单调不降。此时删除前面的数字，只会让不小于它的数字前移，因此删除最后一位即可。

由此得到贪心策略：

1. 从左往右找到第一个比后一位大的数字，删除它。
2. 如果找不到，就删除最后一位。
3. 重复上述操作，直到恰好删除 $k$ 位。

例如样例的删除过程为：

1
2

175438 → 15438 → 1438 → 138 → 13
  删7      删5     删4    删8

最后一步的 138 已经单调递增，因此删除末尾的 8。

为什么这个策略可以连续使用？

只说明「删一位时最优」，还不能直接认为「重复删就一定最优」。我们需要证明：无论还要删除多少位，都存在一个最优方案，包含本轮贪心选择的这一位。

设 $p$ 是第一个下降位置，那么前缀满足

取一个恰好删除 $k$ 位的最优方案。如果它已经删除了 $a_p$，就与本轮选择一致；否则分两种情况讨论：

1. 它在 $p$ 之前删除过某一位 $a_q$。 改为保留 $a_q$、删除 $a_p$，其他删除位置不变。由于 $a_q,\ldots,a_p$ 单调不降，这相当于在保留的前缀中补回一个较小或相等的数字，去掉末尾较大或相等的数字。剩余前缀的每一位都不会变大，后缀不变，所以新方案不劣。
2. 它在 $p$ 之前没有删除任何位。 由于 $a_p$ 也被保留，至少有一个删除位置在 $p$ 之后。设其中最靠左的位置为 $q$，改为保留 $a_q$、删除 $a_p$。若 $q=p+1$，则 $a_{p+1}$ 被恢复；若 $q>p+1$，则 $a_{p+1}$ 原本就被保留。两种情况下，新方案的前 $p-1$ 位都不变，第 $p$ 位却从 $a_p$ 变成了更小的 $a_{p+1}$，结果严格变小。这与原方案最优矛盾。

因此，总能找到一个最优方案删除 $a_p$。固定这次删除后，问题就变成：在剩下的序列中再删除 $k-1$ 位，仍然可以使用同样的策略。

若整个序列单调不降，保留最前面的 $m-k$ 位就能得到最小结果，所以先删除末尾一位也一定能包含在某个最优方案中。

关于前导零

例如 10020 删除一位，先删除第一个下降位置上的 1，得到 0020，输出时应写成 20。

贪心过程中不要额外删除前导零：题目要求恰好删除 $k$ 位，而去掉前导零只是最后输出时的格式处理。若全部剩余数字都是零，则输出一个 0。

复杂度

每次从头查找删除位置，再用字符串的 erase 删除一位，查找和移动字符都需要 $O(m)$ 时间。总时间复杂度为 $O(km)$，最坏为 $O(m^2)$；存储字符串需要 $O(m)$ 空间。

本题最多只有 $250$ 位，直接模拟足够，不需要为了优化而增加实现难度。

3 代码

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

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    int k;
    cin >> s >> k;

    for (int i = 0; i < k; i++) {
        int pos = 0;
        int len = s.size();

        // 越过单调不降的前缀，找到第一个下降位置。
        while (pos + 1 < len && s[pos] <= s[pos + 1]) {
            pos++;
        }
        // 若一直没有下降，pos 恰好停在最后一位。
        s.erase(pos, 1);
    }

    // 恰好删完 k 位后，再处理输出时的前导零。
    int first = 0;
    int len = s.size();
    while (first < len && s[first] == '0') {
        first++;
    }

    if (first == len) {
        cout << 0 << '\n';
    } else {
        cout << s.substr(first) << '\n';
    }
    return 0;
}

4 相关题解

暂无相关题解