删数问题的贪心算法的正确性证明

删数问题是指给定一个正整数序列，每次可以选择其中的一个数并将其删去，最终使得序列中剩余的数组成的数最小。贪心算法可以解决这个问题，其正确性证明如下：

假设当前需要删去一个数，我们应该选择哪一个数呢？显然应该选择最高位最小的数，因为这样可以保证删去这个数后剩余的数字最小。具体来说，假设当前的数列为 $a_1,a_2,\dots,a_n$，我们应该找到最高位最小的数 $a_k$，其中 $k$ 满足 $a_k>0$ 且对于所有 $i<k$，有 $a_i=0$ 或者 $a_i=a_k$。然后删去这个数，并将剩下的数字重新组成一个新的序列。

这个贪心策略是正确的。首先可以证明它是一种可行的策略，即它能够得到一个合法的解。其次可以证明它是一种最优的策略，即它能够得到一个最小的解。

对于可行性，假设我们按照上述策略进行删数，得到了一个序列 $b_1,b_2,\dots,b_m$。我们需要证明这个序列是合法的，即它可以通过删数得到。假设原来的序列是 $a_1,a_2,\dots,a_n$。对于每个 $b_i$，我们可以在原来的序列中找到一个最高位最小的数 $a_j$，满足 $j$ 是尽可能小的满足 $a_j=b_i$ 的下标。由于 $b_i$ 是 $a_j$ 的最高位，因此在 $j$ 之前所有数都为 $0$ 或者与 $b_i$ 相等。因此我们可以将 $a_j$ 删去，并将剩余的数字重新组成一个新的序列。重复这个过程直到所有的 $b_i$ 都被处理完毕。

对于最优性，假设我们按照上述策略进行删数，得到了一个序列 $b_1,b_2,\dots,b_m$。我们需要证明这个序列是最优的，即不存在另外一种删数方案得到的序列比它更小。假设另外一种方案得到的序列为 $c_1,c_2,\dots,c_m$。由于我们按照最高位最小的原则进行选择，因此对于任意 $i$，都有 $b_i \leq c_i$。因此序列 $b_1,b_2,\dots,b_m$ 要么与序列 $c_1,c_2,\dots,c_m$ 相等，要么比它更小。

综上所述，我们证明了贪心算法是正确的，并且可以得到一个最优解。