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

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

题目描述

键盘输入一个高精度的正整数n nn（不超过250 250250位），去掉其中任意k kk个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的n nn和k kk，寻找一种方案使得剩下的数字组成的新数最小。

输入格式

输入两行正整数。

第一行输入一个高精度的正整数n nn。

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

输出格式

输出一个整数，最后剩下的最小数。

输入输出样例 1

输入 1

175438 4

输出 1

13

说明/提示

用len ⁡ ( n ) \operatorname{len}(n)len(n)表示n nn的位数，保证1 ≤ k < len ⁡ ( n ) ≤ 250 1 \leq k < \operatorname{len}(n) \leq 2501≤k<len(n)≤250。

注意：去掉若干数字后剩下的数可以存在前导零，而输出时不要输出前导零。

思路分析

直接贪心删除策略：每次删除一个数字，重复 k 次。
具体思路如下：

1. 循环 k 次：每次删除一个数字，目标是让剩下的数最小。
2. 寻找删除位置：从左到右扫描数字串，找到第一个满足n[j] > n[j+1]的位置 j（即“下降点”）。这个位置上的数字比它右边的数字大，删除它可以减小高位数值。如果整个序列是非递减的（即没有下降点），则删除最后一个数字。
3. 删除操作：用erase(p,1)删除找到的位置 p 上的字符。
4. 去除前导零：删除完成后，如果结果字符串长度大于1且开头是 ‘0’，则循环删除开头的零。
5. 输出结果：输出剩余字符串（若全为零则输出一个“0”）。

代码实现

#include<bits/stdc++.h>// 万能头文件usingnamespacestd;string n;// 存储输入的高精度数字intk;// 需要删除的数字个数intmain(){cin>>n>>k;// 读入数字串和kfor(inti=1;i<=k;i++){// 重复删除k次intp=n.size()-1;// 默认删除最后一个字符（当序列非递减时）for(intj=0;j<=n.size()-2;j++){// 从左到右扫描相邻两位if(n[j]>n[j+1]){// 找到第一个下降点（左边大于右边）p=j;// 记录要删除的位置break;// 立即退出扫描}}n.erase(p,1);// 删除该位置的一个字符}// 去除前导零，但至少保留一个数字（防止全删后为空）while(n.size()>1&&n[0]=='0'){n.erase(0,1);// 删除开头的'0'}cout<<n<<endl;// 输出结果return0;}

功能分析

• 输入：高精度正整数n（字符串形式，长度≤250）和正整数k（k < len(n)）。
• 处理流程：
  1. 重复 k 次删除操作，每次找到第一个“左边>右边”的位置并删除该左边数字；若无下降点则删除末尾数字。
  2. 删除完成后，去掉所有前导零（但若全部为零则保留一个“0”）。
• 输出：删除 k 个数字后能得到的最小数字（无前导零）。
• 正确性：基于贪心原理——每次删除第一个下降点能保证当前步最优，最终结果全局最优。
• 时间复杂度：O(k·len)，在题目限制下（len≤250）完全可接受。
• 空间复杂度：O(len)，仅使用原字符串和几个变量。

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

#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;}