算法课上机作业题目
D17106. 删数
时间限制:3.0s 内存限制:256.0MB
问题描述
现有一个n位数,你需要删除其中的k位,请问如何删除才能使得剩下的数最大?
比如当数为2319274 k=1时,删去2变成319274后是可能的最大值。
输入格式
输入的第一行包含一个整数T,表示数据的组数。
接下来T组数据中:每组输入的仅有一行包含1个n位数以及数k,内容如前所述。
输出格式
对于每组测试数据,输出将n删除k位数后的最大数,数据保证最大数>0。
样例输入
1 | 2 |
样例输出
1 | 880932422 |
数据规模和约定
对于80%的数据,满足 0<n<=2000, k<=min(1000,n-1)。
所有的数据满足 T=40 0<n<=100000, k<=min(1000,n-1)。
「解题思路」
通过分析样例可以分析一个简单的思路,每次从前向后遍历数字,当一个数字小于它后面的数字时可以将它删掉。如果要删除k个数字,那么需要从头到尾遍历 k 次,这样算法复杂度为$O(k*n)$的。对于大数据很明显会超时,所以我们需要对这个算法进行优化,让算法只需要遍历一次字符串就可以删除 k 个数字。
怎么达到这个效果呢?我们需要在删除一个数字后,直接将它之前的一个数字和它后面的数字连在一起,同时对这两个数字进行比较。例如88009,我们需要删除3个数字,我们第一次会删掉第四位的0,88009,这时我们需要将第三位的0和9比较,再将0删除变为88009,再将8和9比较删除8,得到88009。
可以发现我们需要的是链表这种数据结构。所以我们用数组模拟链表,得到算法如下。
需要注意的一个细节就是,如果遍历一遍删除的元素不足 k 个。这个时候字符串已经是降序排列的,所以我们只需要从后向前删除数字,补齐 k 个即可。算法整体复杂度为$O(n+k)$。
AC code
1 |
|