刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

编程实现:

小蓝和小青在玩积木搭建游戏,具体玩法如下:

小蓝报一个数字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

使用微信搜索喵呜刷题,轻松应对考试!

答案:

br />输入一个正整数N,表示小蓝报出的数字,再输入多个正整数,表示已有积木块每一块的高度。我们需要找到最少需要使用的积木块数,使得搭建的高楼高度大于N。

解析:

【喵呜刷题小喵解析】

这个问题可以通过贪心算法来解决。贪心算法是一种在每一步选择中都采取当前情况下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。

在这个问题中,我们可以按照积木块的高度从大到小进行排序,然后依次累加高度,直到累加的高度大于N。此时,我们需要的积木块数就是最少需要使用的积木块数。

具体的算法步骤如下:

1. 对所有积木块按照高度从大到小进行排序。
2. 初始化变量count为0,表示使用的积木块数。
3. 初始化变量sum为0,表示累加的高度。
4. 遍历所有积木块,对于每个积木块,将其高度加到sum上,如果sum大于N,就跳出循环。
5. 如果在遍历过程中没有跳出循环,那么count就是最少需要使用的积木块数。否则,count+1就是最少需要使用的积木块数。

最后,输出count即可。

在上面的例子中,N=12,已有4个积木块的高度分别为4,7,8,4。我们可以按照高度从大到小进行排序,得到7,8,4,4。然后,我们依次累加高度,得到7+8=15,此时累加的高度已经大于N,所以最少需要使用的积木块数为2。
创作类型:
原创

本文链接:编程实现: 小蓝和小青在玩积木搭建游戏,具体玩法如下: 小蓝报一个数字N,代表高楼的高度,小青则需

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share