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