【GESP】C++六级/五级练习题 luogu-P1323 删数问题

GESP C++ 六级/五级练习题，优先队列构造数据集合以及贪心算法的应用，五六级考生均可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。

luogu-P1323 删数问题

题目要求

题目描述

一个集合有如下元素：$1$ 是集合元素；若 $P$ 是集合的元素，则 $2\times P+1$，$4\times P+5$ 也是集合的元素。

取出此集合中最小的 $k$ 个元素，按从小到大的顺序组合成一个多位数，现要求从中删除 $m$ 个数位上的数字，使得剩下的数字最大，编程输出删除前和删除后的多位数字。

注：不存在所有数被删除的情况。

输入格式

只有一行两个整数，分别代表 $k$ 和 $m$。

输出格式

输出为两行两个整数，第一行为删除前的数字，第二行为删除后的数字。

输入输出样例 #1

输入 #1

5 4

输出 #1

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$ 个数字，使得剩下的数最大。

这是一个经典的贪心问题（通常是删数求最小，本题求最大）。

• 原则：为了让剩下的数最大，我们需要让高位数字尽可能大。
• 策略：从左往右遍历数字，如果当前数字比它前面的数字（高位）大，那么删除前面的那个较小数字，能让当前的较大数字“上位”到更高位，从而使得整体数值变大。

具体实现可以使用单调栈（类似于单调递减栈）的思想：

1. 遍历字符串中的每个数字 c。
2. 检查结果字符串（栈）的末尾数字 last。
3. 如果 last < c 并且我们还有删除配额 ($m > 0$)，说明保留 last 不如保留 c（让 c 顶替 last 的位置会让整体变大），因此我们将 last 删除（出栈），并将 $m$ 减 1。
4. 重复步骤 3 直到不满足条件。
5. 将 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。

---

示例代码

#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)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号