【题目来源】
洛谷：P1106 删数问题 - 洛谷 (luogu.com.cn)
【题目描述】
键盘输入一个高精度的正整数 \(N\)（不超过 \(250\) 位），去掉其中任意 \(k\) 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 \(N\) 和 \(k\)，寻找一种方案使得剩下的数字组成的新数最小。
【输入】
输入两行正整数。
第一行输入一个高精度的正整数 \(n\)。
第二行输入一个正整数 \(k\)，表示需要删除的数字个数。
【输出】
输出一个整数，最后剩下的最小数。
【输入样例】
175438
4
【输出样例】
13
【解题思路】
【算法标签】
《洛谷 P1106 删数问题》 #字符串# #贪心#
【代码详解】
#include <bits/stdc++.h> // 包含标准库头文件（万能头文件）
using namespace std; // 使用标准命名空间string s; // 定义字符串：存储输入的数字序列
int n, k, tempi; // 定义变量：数字长度n，删除数字数k，临时存储最小值
int mark = 0, flag = 0; // 定义变量：查找起始位置mark，前导零标记flag/*** 在指定范围内查找最小数字* @param l 查找范围的左边界* @param r 查找范围的右边界* @return 找到的最小数字*/
int find_min(int l, int r)
{int minc = s[l]; // 初始化最小值为左边界字符mark = l + 1; // 更新查找起始位置// 遍历查找范围内的字符for (int i = mark; i <= r; i++) {if (s[i] < minc) // 找到更小的数字{minc = s[i]; // 更新最小值mark = i + 1; // 更新查找起始位置}}return minc - '0'; // 返回数字值（字符转整数）
}int main()
{cin >> s; // 输入数字序列n = s.length(); // 获取数字长度cin >> k; // 输入要删除的数字个数// 构建最小数字序列（保留n-k位）for (int i = 0; i < n - k; i++) {tempi = find_min(mark, k + i); // 查找当前范围内的最小值// 处理前导零情况if (tempi == 0 && flag == 0) {continue;}flag = 1; // 标记已出现非零数字cout << tempi; // 输出当前数字}// 处理全零情况if (flag == 0) cout << 0;return 0; // 程序正常结束
}
【运行结果】
175438
4
13