洛谷P1106(删除数字问题)
发布时间
阅读量:
阅读量
贪心算法,寻找规律
当数字中包含0时,例如50074897,若删除2个数字,则得到的最小数为4897。通过分析可以发现如下规律:
若需要删除k个数字,并且在前k个数字中存在0,那么应当删除最后一个0之前的全部非零数字。这样处理后,剩下的数字可能包含多个前缀0,如50074897中删除5和7后得到004897,其等价于4897。因此,在处理此类情况时应优先解决前k个数字中夹杂着0的问题。完成处理后,若已删除了y个非零数字,则还需继续删除k -= y个非零数字。
当数字中不包含任何0时,则需逐步确定最小数的首位。以175438为例,假设k = 4,则需删除4个数字。首先从17543这五个数字(即下标[0…4])中找到最小值1作为首位,此时剩余的数为75438,并且还需继续删除3个数字。接下来,在7543这四个数(即下标[0…3])中找到最小值3作为次位,此时剩余的数为8,并且还需再删掉1个数字。最终将该位直接删去即可。综上所述,最终保留下来的两个首位分别为1和3,组合成最终结果13
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MaxN = 255
全部评论 (0)
还没有任何评论哟~
