[导读]:超平老师的Scratch蓝桥杯真题解读系列在推出之后,受到了广大老师和家长的好评,非常感谢各位的认可和厚爱。作为回馈,超平老师计划推出《Python蓝桥杯真题解析100讲》,这是解读系列的第83讲。
积木搭建游戏,本题是2022年4月17日举办的第13届蓝桥杯青少组Python编程省赛真题编程部分第3题,13届一共举办了两次省赛,这是第一次省赛。题目要求编程帮助小青找出最少需要多少块积木可以搭建出高度大于N的高楼。
先来看看题目的要求吧。
一.题目说明
编程实现:
小蓝和小青在玩积木搭建游戏,具体玩法如下:
小蓝报一个数字N,代表高楼的高度,小青则需要使用最少的积木建出高度大于N的高楼。给出小蓝所报出的数字N,及已有积木块每一块的高度,请你帮助小青找出最少需要多少块积木可以搭建出高度大于N的高楼。
例如:N = 12时,已有4个积木块的高度分别为4, 7, 8, 4则最少需要2块积木,可以使搭建的高楼高度大于12,2块积木为7和8。
输入描述:
第一行输入一个正整数N,表示小蓝报出的数字。
第二行输入多个正整数,表示已有积木块每一块的高度,正整数之间以一个英文逗号隔开。(要求所有正整数之和大于N)
输出描述:
输出最少需要使用多少块积木,可以搭建出高度大于N的高楼。
输入样例:
12
4,7,8,4
输出样例:
2
二.思路分析
这是一道简单的算法题,涉及的知识点包括循环、条件、列表和贪心算法等。
要确保积木块的数量最少,那么我们尽量要选择高度最大的积木块,这正是贪心算法的核心思想。
贪心算法,又称贪婪算法,英文名greedy algorithm。
贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,它期望通过局部最优选择得到全局最优的解决方案。
以题目中的样例数据为例,4个积木块的高度分别为4, 7, 8, 4,要搭建的高楼高度为12。
首先我们选择最高的积木块8,同时计算出已搭建高度为8,8 < 12,然后在剩余的积木块中选择最高的积木块7,此时已搭建高度为8 + 7 = 15,由于15 > 12,满足条件,所以只需要两个积木块。
因此,我们可以对所有积木块按照从大到小的顺序排序,然后依次取出每一个积木块,累加其高度,当总高达大于N时,结束循环。
在这个过程中,我们每次选择当前最高的积木块,这样可以确保每次选择的都是当前最优的解决方案。
通过贪心算法,我们可以快速找到最少需要的积木块数,从而搭建一个高度大于N的高楼。
思路有了,接下来,我们就进入具体的编程实现环节。
三.编程实现
根据上面的思路分析,我们编写程序如下:
代码不多,强调两点:
1). 在获取输入的数字字符串时,使用了列表推导式的编程技巧,你也可以使用map()函数来实现,写法如下:
height = list(map(int, input().split(',')))
2). sort()函数默认是从小到大排序,通过关键词参数reverse=True可以实现从大到小排序;
至此,整个程序就全部完成了,你可以输入不同的数据来测试效果啦。
四.总结与思考
本题代码在10行左右,涉及到的知识点包括:
-
循环语句;
-
条件语句;
-
列表操作;
-
贪心算法;
本题代码不多,难度一般,关键有两点,一是理解贪心算法的核心思想及其特点,二是灵活运用sort()函数对列表排序。
尽管贪心算法很简单且高效,但并非所有问题都适合使用贪心算法求解。在某些情况下,贪心算法无法得到最优解,因为它的局部选择不能保证总体的最优性。
因此,对于每个具体问题,都需要具体问题具体分析,评估贪心算法是否适用。
你还有什么好的想法和创意吗,也非常欢迎和超平老师分享探讨。
如果你觉得文章对你有帮助,别忘了点赞和转发,予人玫瑰,手有余香😄
需要源码的,可以移步至“超平的编程课”gzh。