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

csp信奥赛C高频考点专项训练之贪心算法 --【删数问题】删数问题题目描述键盘输入一个高精度的正整数n nn不超过250 250250位去掉其中任意k kk个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的n nn和k kk寻找一种方案使得剩下的数字组成的新数最小。输入格式输入两行正整数。第一行输入一个高精度的正整数n nn。第二行输入一个正整数k kk表示需要删除的数字个数。输出格式输出一个整数最后剩下的最小数。输入输出样例 1输入 1175438 4输出 113说明/提示用len ⁡ ( n ) \operatorname{len}(n)len(n)表示n nn的位数保证1 ≤ k len ⁡ ( n ) ≤ 250 1 \leq k \operatorname{len}(n) \leq 2501≤klen(n)≤250。注意去掉若干数字后剩下的数可以存在前导零而输出时不要输出前导零。思路分析直接贪心删除策略每次删除一个数字重复 k 次。具体思路如下循环 k 次每次删除一个数字目标是让剩下的数最小。寻找删除位置从左到右扫描数字串找到第一个满足n[j] n[j1]的位置 j即“下降点”。这个位置上的数字比它右边的数字大删除它可以减小高位数值。如果整个序列是非递减的即没有下降点则删除最后一个数字。删除操作用erase(p,1)删除找到的位置 p 上的字符。去除前导零删除完成后如果结果字符串长度大于1且开头是 ‘0’则循环删除开头的零。输出结果输出剩余字符串若全为零则输出一个“0”。代码实现#includebits/stdc.h// 万能头文件usingnamespacestd;string n;// 存储输入的高精度数字intk;// 需要删除的数字个数intmain(){cinnk;// 读入数字串和kfor(inti1;ik;i){// 重复删除k次intpn.size()-1;// 默认删除最后一个字符当序列非递减时for(intj0;jn.size()-2;j){// 从左到右扫描相邻两位if(n[j]n[j1]){// 找到第一个下降点左边大于右边pj;// 记录要删除的位置break;// 立即退出扫描}}n.erase(p,1);// 删除该位置的一个字符}// 去除前导零但至少保留一个数字防止全删后为空while(n.size()1n[0]0){n.erase(0,1);// 删除开头的0}coutnendl;// 输出结果return0;}功能分析输入高精度正整数n字符串形式长度≤250和正整数kk len(n)。处理流程重复 k 次删除操作每次找到第一个“左边右边”的位置并删除该左边数字若无下降点则删除末尾数字。删除完成后去掉所有前导零但若全部为零则保留一个“0”。输出删除 k 个数字后能得到的最小数字无前导零。正确性基于贪心原理——每次删除第一个下降点能保证当前步最优最终结果全局最优。时间复杂度O(k·len)在题目限制下len≤250完全可接受。空间复杂度O(len)仅使用原字符串和几个变量。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}