csp信奥赛C++高频考点专项训练之贪心算法 --【删数问题】：删数问题2

csp信奥赛C++高频考点专项训练之贪心算法 --【删数问题】：删数问题2

题目描述

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

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

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

输入格式

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

输出格式

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

输入输出样例 1

输入 1

5 4

输出 1

137915 95

数据规模与约定

• 对于30 % 30\%30%的数据，保证1 ≤ k , m ≤ 300 1\le k,m\le3001≤k,m≤300。
• 对于100 % 100\%100%的数据，保证1 ≤ k , m ≤ 3 × 10 4 1\le k,m\le3\times10^41≤k,m≤3×104。

思路分析

1. 生成最小的 k 个集合元素
   集合定义：1 在集合中；若 P 在集合中，则 2P+1 和 4P+5 也在集合中。
   要得到最小的 k 个元素，可以使用最小堆（优先队列）进行 BFS。

   • 初始将 1 入堆，并用哈希集合记录已生成的数，避免重复。
   • 每次弹出堆顶（当前最小值），将其加入结果数组，然后生成两个新数，若未出现过则入堆。
   • 重复 k 次即得到有序的前 k 个元素。

2. 拼接成多位数
   将每个元素转换为字符串，按顺序拼接得到长字符串 s。

3. 删除 m 个数字使剩下的数字最大
   经典贪心问题：使用单调栈。

   • 遍历 s 的每个字符 c，当栈非空且栈顶字符 < c 且还有删除次数时，弹出栈顶（删除该数字），删除次数减 1。
   • 将 c 压入栈。
   • 遍历结束后若还有删除次数，从栈末尾删除相应个数。
     最终栈内字符即为所求的最大数字串。

4. 输出
   第一行输出删除前的多位数 s，第二行输出删除后的多位数。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){intk,m;cin>>k>>m;// 最小堆生成最小的k个元素priority_queue<longlong,vector<longlong>,greater<longlong>>pq;// 最小堆unordered_set<longlong>vis;// 去重vector<longlong>a;// 存放取出的元素pq.push(1);vis.insert(1);while(a.size()<k){longlongx=pq.top();pq.pop();a.push_back(x);longlongy1=2*x+1;longlongy2=4*x+5;if(!vis.count(y1)){pq.push(y1);vis.insert(y1);}if(!vis.count(y2)){pq.push(y2);vis.insert(y2);}}// 拼接成多位数string s;for(longlongv:a){s+=to_string(v);}// 贪心删除m个数字使剩余最大string st;// 栈intd=m;for(charc:s){while(d>0&&!st.empty()&&st.back()<c){st.pop_back();d--;}st.push_back(c);}if(d>0)st.erase(st.end()-d,st.end());// 输出cout<<s<<"\n"<<st<<"\n";return0;}

功能分析

• 生成模块：使用最小堆和哈希集合，时间复杂度 O(k log k)，空间复杂度 O(k)，生成前 k 个最小元素并保持有序。
• 拼接模块：遍历元素数组，调用to_string并连接，总长度 S 约为 k 乘以平均位数（对于 k=3e4，S 约 2e5），时间 O(S)。
• 删除模块：单遍扫描字符串，利用栈维护单调递减趋势，时间复杂度 O(S)，空间复杂度 O(S)。
• 输出模块：直接输出两个字符串。

正确性：贪心删除策略保证了每次删除使剩余数字尽可能大的局部最优，全局最优由单调栈性质保证。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}