浩森宇特北京网站设计,徐州网站制作建设,优化百度搜索,能发布自做的视频网站2025 - 01 - 22 - 第 46 篇 【洛谷】贪心算法题单 - 【贪心算法】 - 【学习笔记】 作者(Author): 郑龙浩 / 仟濹(CSND账号名)
目录 文章目录 目录P1106 删数问题题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示思路代码 P1106 删数问题
题目描述
键盘输入一个高…2025 - 01 - 22 - 第 46 篇 【洛谷】贪心算法题单 - 【贪心算法】 - 【学习笔记】 作者(Author): 郑龙浩 / 仟濹(CSND账号名)
目录 文章目录 目录P1106 删数问题题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示思路代码 P1106 删数问题
题目描述
键盘输入一个高精度的正整数 n n n不超过 250 250 250 位去掉其中任意 k k k 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 n n n 和 k k k寻找一种方案使得剩下的数字组成的新数最小。
输入格式
输入两行正整数。
第一行输入一个高精度的正整数 n n n。
第二行输入一个正整数 k k k表示需要删除的数字个数。
输出格式
输出一个整数最后剩下的最小数。
样例 #1
样例输入 #1
175438
4样例输出 #1
13提示
用 len ( n ) \operatorname{len}(n) len(n) 表示 n n n 的位数保证 1 ≤ k len ( n ) ≤ 250 1 \leq k \operatorname{len}(n) \leq 250 1≤klen(n)≤250。
思路 删除任意k个数字以后如何保证是最小的数呢如何去掉呢 思路是这样的从做往右(高位到低位)依次两两比较如果 arr[ i ] arr[ i 1 ], 则无需管直到遇到 arr[ i ] arr[ i 1 ], 这时候需要将 arr[ i 1 ] 去掉 说白了就是尽量让这个数字保持升序这样才能保证最小 -- 高位数字小 -- 则整个数字小 所以去掉的数字一般分为两种情况 在 i ~ num - 1 的范围内, 【有】 arr[ i ] arr[ i 1 ] 的清况 -- 去掉arr[ i 1 ]在 i ~ num - 1 的范围内, 【无】 arr[ i ] arr[ i 1 ] 的清况 -- 去掉最后一位 -- 为什么是去掉最后一位呢因为数字顺序为升序的时候最右侧的数字是最大的所以去掉 ( 第 2 种情况 也无需再单独去判断了因为内层循环中如果找不到arr[ i ] arr[ i 1 ]退出循环的时候i 会定位在 倒数第二个元素上面 ) 最右侧的数字相当于 -- 整个高精度正数少了一位 少了最大的数 程序过程 最外层循环用来控制循环次数 -- 循环 k 次 -- 删掉 k 个数字最内层循环用来寻找 arr[ i ] arr[ i 1 ] 的情况如果遇到则退出循环将 i 定位在 5 处( 比如 1 2 3 4 5 1 ),退出循环以后将 5 删除即可 借用的函数: erase(a, b) -- 删除函数 -- STL容器 高峰期– 我的理解就是 从左往右依次两两比较只要遇到不是 arr[ i ] arr[ i 1 ] 而是 arr[ i ] arr[ i 1 ], 则 arr[ i ] 就是这个高峰期 简单点说,就是尽可能的让高位数字的顺序为升序 -- 因为 高位数字小, 则整个 高精度数字 就小 变量 arr -- 存放高精度正整数 k -- 要删除的数字的数量 i -- 决定 高峰 的位置 代码
// 洛谷P1106 删数问题
// 作者: 郑龙浩 / 仟濹(CSDN)
// 时间2025 - 01 -22
// 键盘输入一个高精度的正整数 n不超过 250 位去掉其中任意 k 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 n 和 k
// 寻找一种方案使得剩下的数字组成的新数最小。// 看的这个大佬的题解我才会这么做的 https://www.luogu.com.cn/article/qgschm0n// 思路:
// 删除任意k个数字以后如何保证是最小的数呢如何去掉呢
// 思路是这样的从做往右(高位到低位)依次两两比较如果 arr[ i ] arr[ i 1 ], 则无需管直到遇到 arr[ i ] arr[ i 1 ], 这时候需要将 arr[ i 1 ] 去掉
// 说白了就是尽量让这个数字保持升序这样才能保证最小 -- 高位数字小 -- 则整个数字小// 所以去掉的数字一般分为两种情况
// 1. 在 i ~ num - 1 的范围内, 【有】 arr[ i ] arr[ i 1 ] 的清况 -- 去掉arr[ i 1 ]
// 2. 在 i ~ num - 1 的范围内, 【无】 arr[ i ] arr[ i 1 ] 的清况 -- 去掉最后一位 -- 为什么是去掉最后一位呢因为数字顺序为升序的时候最右侧的数字是最大的所以去掉
// ( 第 2 种情况 也无需再单独去判断了因为内层循环中如果找不到arr[ i ] arr[ i 1 ]退出循环的时候i 会定位在 倒数第二个元素上面 )// 最右侧的数字相当于 -- 整个高精度正数少了一位 少了最大的数、
// 程序过程
// 1. 最外层循环用来控制循环次数 -- 循环 k 次 -- 删掉 k 个数字
// 2. 最内层循环用来寻找 arr[ i ] arr[ i 1 ] 的情况如果遇到则退出循环将 i 定位在 5 处( 比如 1 2 3 4 5 1 ),退出循环以后将 5 删除即可//借用的函数erase(a, b) -- 删除函数 -- STL容器// 高峰期 -- 我的理解就是 从左往右依次两两比较只要遇到不是 arr[ i ] arr[ i 1 ] 而是 arr[ i ] arr[ i 1 ], 则 arr[ i ] 就是这个高峰期
// 简单点说,就是尽可能的让高位数字的顺序为升序 -- 因为 高位数字小, 则整个 高精度数字 就小// 变量
// arr -- 存放高精度正整数
// k -- 要删除的数字的数量
// i -- 决定 高峰 的位置#include iostream
#include algorithm
#include string
using namespace std;
int main( void ){string arr; // 表示的 高精度正整数int k; // 表示的 要删除的数字数量cin arr k;while( k ){// 寻找 高峰期int i;for( i 0; arr[ i ] arr[ i 1 ] i arr.size() - 1; i ); // 非常简洁 -- 寻找 高峰期(第一次知道这个词语从题解中看到的因为我自己不知道用什么词语可以表达找到的这个元素)arr.erase( i, 1 ); // 从第 i 个位置连续删 1 个元素k --;}// 处理前导零 -- 如果本来的 高精度正整数 前面几个为0,则不能将其打出来, 应该将它们去掉while( arr [ 0 ] 0 arr.size() 1 ) {//处理前导零, 并且保证如果数字为0,则必须保留一位0 arr.erase( 0, 1 );}cout arr;return 0;
}
