贪心算法删除数字求最小值

贪心算法是指在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，从而希望得到全局最好或最优的算法。在删除数字求最小值问题中，贪心算法的应用能够有效地简化问题，提高效率。

1.问题描述

在一个数字串中，删除k个数字，使得剩下的数字组成的新数字串最小。如何实现？

2.算法思路

设目前数字组成的新数字串为ans字符串，从左到右扫描数字串：

(1)如果新数字串ans的长度小于k，则向ans中添加该数字(j)；

(2)如果新数字串ans的长度不小于k，如果当前数字比ans中最后一个数字小，则删除ans中最后一个数字，重复步骤(2)直到不需要再删除数字或删除了k个数字后。

3.算法证明

为证明该算法是正确的，我们需要证明：每次选择当前最优解，最终得到的解一定是全局最优解。

设当前考虑的数字串为num，删除后的数字串长度为len，从num的左端开始选取消息构成新的数字串ans，并且保证ans的长度不大于len。当前已删除的数字个数为count，那么应当尽量使得新数字串ans的第1个数字最小，次之是ans的第2个数字最小，以此类推。

如果在ans中的最后一个数字比当前数字num[i]要大，那么删除ans中的最后一个数字。直到ans中的最后一个数字num[k]，使得num[k]-num[i]的结果尽可能的小。如果提示所有的数字都扫描完毕，但是还没有达到删除数字的要求，那么应当在已经构建的ans串的末尾删去前面的数字直到达到要求。

这样构建出的ans串必定是删除数字后最小的方案，而且每次操作都是最优的。所以该算法得出的结果一定是全局最优解。

4.算法实现

接下来，根据以上思路，我们实现贪心算法删除数字求最小值。其中，需要考虑的问题包括如何输入数字串、如何输入k值、如何输出结果、如何优化算法效率等。

具体代码如下：

```

#include

#include

#include

using namespace std;

const int N = 1e5+10; // 数组要大一点

char s[N], ans[N]; // 存原始数字串和新数字串

int k; // 删除数字的个数

int main()

{

scanf("%s%d", s, &k);

int len = strlen(s); // 计算数字串的长度

int top = 0; // 指向新数字串的末尾

for (int i = 0; i < len; i ++ )

{

// 若删除的数字还未达到k，则直接添加进新数字串中

while (top && s[i] < ans[top - 1] && k > 0) top -- , k -- ;

// 添加数字进新数字串

if (top < len - k) ans[top ++ ] = s[i];

}

// 输出结果

ans[top] = '\0'; // 结束符

puts(ans);

return 0;

}

```

5.算法优化

实际上，我们可以进行更多的优化，以提高算法效率。

首先，可以将数组的类型由char[]改为int[]，并在输入时将字符转换为整数。这样可以避免字符和数字的频繁转换，提高程序效率。

其次，可以将数组的容量稍作扩大，减少数组动态扩容的操作。这样可以避免频繁的内存分配和释放操作，提高程序效率。

再次，可以添加数组越界判断，以避免因操作不当导致的程序错误。这样可以提高程序健壮性。

最后，可以添加程序运行时间统计、程序调试信息输出等功能，以便更准确地了解程序运行状态。这样可以提高程序的调试和优化效率。

6.