C++解决删数问题,找到剩余数字组成的最小正整数

需积分: 50 21 下载量 36 浏览量 更新于2024-10-04 1 收藏 828B TXT 举报
"C++ 贪心算法 删数问题" 在计算机科学中,贪心算法是一种在每一步选择中都采取当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。在这个C++程序中,我们看到一个具体的贪心算法应用,用于解决“删数问题”,即从一个正整数中删除若干个数字,使得剩下的数字组成的新数尽可能小。 题目要求是:给定一个包含n个数字的正整数a,需要从中删除k个数字(k≤n),目标是找到删除这些数字后的最小正整数。程序通过读取输入的a和k来处理这个问题。 在程序代码中,首先定义了必要的变量,如`int i, n, k, m, p, l, j`以及字符串`s`和字符数组`q`。接着,使用一个`while`循环处理多组测试用例。在循环内部,首先将输入的字符串`s`存储到`q`中,然后初始化一些变量。 核心的贪心策略在于,从第二个数字开始遍历,如果当前数字小于已选择的最小数字,则替换它;否则,如果当前数字大于已选择的最小数字,就将当前数字插入到已选择数字序列中的合适位置,以保持序列的非降序排列。这个过程会确保删除k个数字后剩余的数字序列是尽可能小的。 在遍历过程中,当遇到比已选数字小的数字时,会使用一个`for`循环在已选数字序列中找到合适的插入位置。当所有数字都被处理后,删除前导的零(因为目标是最小正整数,前导零可以被忽略),然后输出结果。 需要注意的是,此程序仅适用于非负整数,并且在处理输入时假设输入是有效的。在实际应用中,通常需要增加错误检查以确保输入的正确性。 这个贪心算法的问题解决方案展示了如何在有限步长内做出局部最优决策,以期望达到全局最优解。贪心算法在很多优化问题中都有广泛的应用,例如最小生成树问题、活动选择问题等。不过,贪心算法并不总是能给出全局最优解,只有在问题的最优解可以通过局部最优解构建时,贪心算法才是有效的。在这个特定的删数问题中,由于我们始终选择当前最小的数字,因此贪心算法可以保证得到全局最小解。