【GESP】C++六级/五级练习题 luogu-P1323 删数问题
GESP C++ 六级/五级练习题，优先队列构造数据集合以及贪心算法的应用，五六级考生均可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。
luogu-P1323 删数问题
题目要求
题目描述
一个集合有如下元素：$1$ 是集合元素；若 $P$ 是集合的元素，则 $2\times P+1$，$4\times P+5$ 也是集合的元素。
取出此集合中最小的 $k$ 个元素，按从小到大的顺序组合成一个多位数，现要求从中删除 $m$ 个数位上的数字，使得剩下的数字最大，编程输出删除前和删除后的多位数字。
注：不存在所有数被删除的情况。
输入格式
只有一行两个整数，分别代表 $k$ 和 $m$。
输出格式
输出为两行两个整数，第一行为删除前的数字，第二行为删除后的数字。
输入输出样例 #1
输入 #1
1
5 4
输出 #1
1
2
137915
95
说明/提示
数据规模与约定
- 对于 $30\%$ 的数据，保证 $1\le k,m\le300$。
- 对于 $100\%$ 的数据，保证 $1\le k,m\le3\times10^4$。
题目分析
本题包含两个主要部分：集合元素的生成和贪心策略删数。
1. 集合元素的生成（优先队列）
题目定义的集合生成规则如下：
- $1$ 是初始元素。
- 若 $P$ 在集合中，则 $2 \times P + 1$ 和 $4 \times P + 5$ 也在集合中。
我们需要找到集合中最小的 $k$ 个元素。在元素生成上适合使用小根堆（优先队列） 来维护。
- 使用
std::priority_queue（配合greater比较器）来存储当前的候选元素。 - 初始时将 $1$ 入队。
- 每次取出队首元素（当前最小值）$x$，将其加入结果集。
- 然后计算 $2x+1$ 和 $4x+5$ 并加入队列。
- 重复此过程直到收集满 $k$ 个元素。
- 注意：为了避免重复元素入队（虽然本题的生成公式在特定范围内不易重复，但严谨起见），可以在取出元素时判断是否与上一个加入结果集的元素相同，若相同则跳过。
2. 贪心策略删数（单调栈）
将生成的 $k$ 个数拼接成一个长字符串后，问题转化为：删除 $m$ 个数字，使得剩下的数最大。
这是一个经典的贪心问题（通常是删数求最小，本题求最大）。
- 原则：为了让剩下的数最大，我们需要让高位数字尽可能大。
- 策略：从左往右遍历数字，如果当前数字比它前面的数字（高位）大，那么删除前面的那个较小数字，能让当前的较大数字“上位”到更高位，从而使得整体数值变大。
具体实现可以使用单调栈（类似于单调递减栈）的思想：
- 遍历字符串中的每个数字
c。 - 检查结果字符串（栈）的末尾数字
last。 - 如果
last < c并且我们还有删除配额 ($m > 0$)，说明保留last不如保留c（让c顶替last的位置会让整体变大），因此我们将last删除（出栈），并将 $m$ 减 1。 - 重复步骤 3 直到不满足条件。
- 将
c加入结果字符串（入栈）。
特殊情况处理：
- 如果遍历完所有数字后，$m$ 仍大于 0（说明整个序列已经是单调递减或相等），此时应该从末尾删除剩余的 $m$ 个数字，因为末尾数字对数值大小贡献最小。
示例推导： 假设数字串为 137915，$m=4$。
- ‘1’ 入栈 ->
1 - ‘3’:
1 < 3，删1，余 $m=3$ ->3 - ‘7’:
3 < 7，删3，余 $m=2$ ->7 - ‘9’:
7 < 9，删7，余 $m=1$ ->9 - ‘1’:
9 > 1，不删 ->91 - ‘5’:
1 < 5，删1，余 $m=0$ ->95 - 结束，输出
95。
示例代码
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
// 优先队列保证每次取出最小的元素
priority_queue<int, vector<int>, greater<int>> pq;
// 存储生成的最小的k个数
vector<int> nums;
int main() {
int k, m;
cin >> k >> m;
// 1. 构造数据：生成集合中最小的k个元素
// 初始元素1入队
pq.push(1);
// 循环取出最小元素并生成新元素，直到收集满k个
// 注意：虽然题目生成规则下不易产生重复，但为了严谨通常可以判重
// 这里因为是严格递增取出的，可以简单判断是否等于上一个取出的数
while (nums.size() < k) {
int x = pq.top();
pq.pop();
// 如果和上一个存入的数相同，则是重复元素，跳过
if (!nums.empty() && nums.back() == x) {
continue;
}
nums.push_back(x);
// 生成新元素加入队列
// 题目保证k<=30000，为了防止int溢出，可以稍微留意一下，但此处2*P+1在k=30000时也不会溢出int
pq.push(2 * x + 1);
pq.push(4 * x + 5);
}
// 将这k个数按顺序拼接成一个大整数（字符串形式）
string s = "";
for (int x : nums) {
s += to_string(x);
}
// 输出删除前的数字
cout << s << endl;
// 2. 删数逻辑：删除m个数字，使得剩下的数最大
// 贪心策略：若高位数字小于后一位数字，则删除该高位数字
// 使用单调递减栈的思想：
// 遍历字符串中的每个字符 c
// 如果 ans 的最后一位数字 < c，并且还有删除次数(m>0)，说明删除 ans
// 末尾的数字能让更大的 c 占据高位，更优
string ans = "";
for (char c : s) {
// 当还有删除机会，且栈非空，且栈顶元素小于当前元素 c 时
while (m > 0 && !ans.empty() && ans.back() < c) {
ans.pop_back(); // 删除栈顶较小的数字
m--; // 消耗一次删除机会
}
ans.push_back(c);
}
// 如果遍历完后 m 仍大于 0，说明已经是非递减序列（或者所有逆序对都删完了），
// 此时应该从末尾删除剩余的 m 个数字（因为末尾是最小的或者对高位影响最小的）
while (m > 0 && !ans.empty()) {
ans.pop_back();
m--;
}
// 输出删除后的最大数
cout << ans << endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
