删数问题
给定一个高精度正整数,在不改变剩余数字原来顺序的情况下删除其中任意 k 个数字,要求最后剩下的数尽可能小。
原题:洛谷 P1106《删数问题》
例如:
175438
4
删除 4 个数字以后,最小结果为:
13
这是一道比较典型的贪心。
思路
设原数为:
因为所有数字删除以后,剩余数字之间的相对顺序不能改变,所以最后实际上是在原序列中保留一个长度为:
的子序列,并且要求这个子序列表示的整数最小。
整数比较首先比较最高位,其次才是下一位。因此越靠前的位置对最终结果影响越大。
所以删除数字的时候,应该尽量让较小的数字提前。
如果从左往右第一次出现:
num[i] > num[i + 1]
那么应该删除:
num[i]
让后面的较小数字 num[i + 1] 提前一位。
例如:
175438
从左往右:
1 < 7
7 > 5
第一次出现下降的位置是:
7 > 5
所以删除 7:
15438
然后重新从左往右寻找第一个下降的位置,继续删除。
重复 k 次即可。
为什么一定删除第一个下降位置
这里可以稍微证明一下。
假设第一次出现:
也就是说:
但是到了这里第一次发生下降:
如果删除 $a_i$,得到的前缀为:
如果不删除 $a_i$,而是去删除后面某一个位置,那么结果的前 $i$ 位仍然是:
两种结果在前 $i-1$ 位完全相同,而第 $i$ 位分别是:
因为:
所以删除 $a_i$ 得到的数字一定更小。
这其实就是整数从高位到低位比较大小的规则。后面的数字不管怎么变化,都无法弥补更高位已经变大的影响。
因此只要出现:
num[i] > num[i + 1]
就应该优先删除前面的 num[i]。
而且要删除的是第一个这样的数字,因为越靠前的位权越大。
从位权看
如果一个长度为 n 的十进制数写成:
那么越靠前的数字乘上的 $10$ 的幂越大。
例如六位数:
abcdef
实际上就是:
所以让一个较小的数字提前一位,影响的是更高数量级。
例如:
175438
删除 7:
15438
而如果保留 7 去删除后面的某个数字,那么第二位仍然是 7。
因为:
15...
<
17...
后面无论是什么都已经不用比较了。
这就是这个贪心成立的原因。
如果没有下降位置
如果整个数字从左往右都是单调不减的,例如:
123456
不存在:
num[i] > num[i + 1]
那么应该直接删除最后一个数字。
得到:
12345
为什么?
因为这时有:
如果删除前面的某一位,就会让它后面一个大于等于它的数字提前。
例如:
123456
删除 3:
12456
而删除最后一个 6:
12345
比较到第三位就已经有:
3 < 4
所以显然删除最后一位更小。
代码里面我没有单独写:
if (没有找到下降位置)
删除最后一个;
因为每一轮最后都会执行:
len--;
如果前面找到了:
num[i] > num[i + 1]
就先把后面的数字整体向左移动一位,再执行 len--。
如果整轮都没有找到,那么数组没有发生移动,最后的:
len--;
自然就相当于删掉最后一个数字。
为什么可以重复贪心
题目不是只删除一个数字,而是要删除 k 个。
第一次按照上面的规则删除以后,会得到一个新的、更短的数字。
例如:
175438
第一次:
7 > 5
删除 7:
15438
现在问题又变成:
从
15438中继续删除剩下的数字,使最后结果最小。
问题的形式完全没有改变。
所以每删除一个数字以后,都重新从左往右寻找新的第一个下降位置即可。
例如:
175438
↓
15438
↓
1438
↓
138
↓
13
最终得到:
13
这就是贪心不断缩小问题规模的过程。
前导零
删除数字以后可能会出现:
00123
虽然内部可以保留这些零,但最后输出整数时应该输出:
123
所以最后从头开始跳过所有的:
'0'
如果剩下的数字全部都是 0,例如:
000
则直接输出:
0
不能什么都不输出。
为什么用字符数组
题目中的数字可能非常长,普通的:
int
long long
都不能直接保存。
但是这道题根本不需要真正进行高精度加减乘除。
我们只需要:
比较相邻数字
删除某一位
移动后面的数字
处理前导零
所以直接把整个数当成字符串或者字符数组处理最方便。
例如:
char num[260];
每一个:
num[i]
就是一个十进制数字字符。
而字符 '0' 到 '9' 的编码顺序也是递增的,所以可以直接写:
if (num[i] > num[i + 1])
不需要专门转换成整数。
代码
#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;
}
复杂度
设原数字长度为 n。
每删除一个数字,都需要从左往右寻找第一个下降位置,最坏需要:
找到以后,还需要把后面的字符向前移动,同样最坏是:
一共删除 k 次,所以总时间复杂度大约为:
因为:
所以最坏也可以写成:
空间上只使用了保存原数字的字符数组,因此额外空间复杂度为:
这道题的数据范围很小,这种直接删除和移动数组的写法已经足够。
总结
这题的核心其实就是十进制整数的比较规则:
高位优先。
如果出现:
num[i] > num[i + 1]
那么把 num[i] 删除以后,可以让一个更小的数字提前到更高位。
因此贪心策略就是:
从左向右扫描
↓
找到第一个 num[i] > num[i + 1]
↓
删除 num[i]
↓
重新扫描
↓
重复 k 次
如果不存在下降位置,说明当前数字单调不减,那么删除最后一位。
最后再处理前导零即可。
这题虽然代码很短,但贪心真正要说明白的地方不是“这样做能过”,而是为什么第一次出现下降时,就可以确定这一位应该优先被删除。
本质上还是因为:
高位发生一次更小的变化,优先级高于后面低位的调整。
所以整个算法实际上是在不断想办法:
让更小的数字尽可能早地出现在更高的位置。
- 本文链接:
- https://bacteriajun.cn/shanshu.html
- 版权声明:本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。
-
支付宝扫一扫
-
微信扫一扫

















这一切,似未曾拥有