删数问题 #

1. 删数问题的介绍
2. 删数问题的算法分析
3. 删数问题的代码实现

删数问题的介绍 #

输入一个高精度的正整数n，去掉任意s个数字后，按原数字的左右次序，组成一个新的正整数。对于给定的n和s，寻找一种方案使得剩下的数字组成的新数字最小。

删数的算法分析 #

一个比较直观的感觉就是每次删除n中最大的一个数字，这个是比较容易举出反例的，例如正整数1839去除1位数字，按照上述策略为183，显然大于139。因此该策略不具备可行性。
贪心策略的制定,应该每一步都尽量把排在前面的交大的数字给去掉：
1）第一步的删除的一个数字应该使剩下的数字最小，即按照高位到地位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区的首数字
2）回到数字首部，按照第一步继续操作，直到删除s个数字。
例如n=175438，s=4 (1)175438、删除7 (2)15438、删除5 (3)1438、删除4 (4)138、删除8 最后得到最小值13

删数的代码实现 #

n,s=input().split()#输入n和s
listn=[int(i) for i in n]#将字符串n转为listn
s=int(s)
for i in range(s):#一共去掉s次数字
	for j in range(len(listn)-1):#每次把排在前面比上一位大的数字去除
		if listn[j]>listn[j+1]:
			listn.pop(j)
			break
	else:#如果是依次递增，把最后一位去除
		listn.pop(j+1)
print(listn)#输出结果,可自行将列表转化为一个数字

小结 #

• 根据删数问题，理解贪心算法
• 掌握删数求解的贪心算法，能够根据实际问题作出合适的贪心策略

习题 #

1. 给定一个正整数N，求最小的、比N大的正整数M，使得M与N的二进制表示中有相同数目的1。
   例如N为78，其二进制表示为1001110，包含四个1，那么最小的比N大的且与N二进制个数一样的为83，其二进制表示为1010011，则83就是答案