删数问题

给定一个高精度正整数，在不改变剩余数字原来顺序的情况下删除其中任意 k 个数字，要求最后剩下的数尽可能小。

例如：

175438
4

删除 4 个数字以后，能够得到的最小结果为：

思路

这题的关键是每次应该删除哪个数字。

因为一个数越靠前的位权越大，所以如果从左往右出现：

num[i] > num[i + 1]

那么保留前面的较大数字肯定不如让后面较小的数字提前，因此可以直接删除 `num[i]`。

例如：

从左往右看：

1 < 7
7 > 5

所以第一次删除 `7`，得到：

然后重新从左往右寻找第一个前一位大于后一位的位置，继续删除。重复 k 次即可。

如果整个数字从左到右都是递增的，例如：

这时前面已经没有可以通过删除来降低高位数字的位置，所以直接删除最后一位即可。

代码里面没有单独再判断这种情况。每轮无论前面有没有发生移动，最后都会执行一次 `len--`。如果找到了需要删除的位置，前面的循环已经把后面的数字整体向左移动；如果没有找到，`len--` 就相当于直接去掉最后一个数字。

前导零

删除数字以后还有一种情况，例如最后结果变成：

输出时显然应该是：

所以最后从头开始跳过所有的 `0`。如果剩下的数字全部都是 `0`，则直接输出一个 `0`。

代码

#include <iostream>
#include <cstring>
using namespace std;

char num[260];

int main()
{
    int n;
    int len;

    cin >> num >> n;
    len = strlen(num);

    while (n--)
    {
        for (int i = 0; i <= len - 2; i++)
        {
            if (num[i] > num[i + 1])
            {
                for (int j = i; j <= len - 2; j++)
                    num[j] = num[j + 1];

                break;
            }
        }

        len--;
    }

    int i = 0;

    while (i <= len - 1 && num[i] == '0')
        i++;

    if (i == len)
        cout << "0";
    else
    {
        for (int j = i; j <= len - 1; j++)
            cout << num[j];
    }

    return 0;
}