硬币（2024.3四级）宇航员 Bob 有一天来到火星上，他有收集硬币的习惯。于是他将火星上所

简答题

硬币（2024.3四级）

宇航员 Bob 有一天来到火星上，他有收集硬币的习惯。于是他将火星上所有面值的硬币都收集起来了，一共有 n 种，每种只有一个：面值分别为 a₁,a₂… a_n。 Bob 在机场看到了一个特别喜欢的礼物，想买来送给朋友 Alice，这个礼物的价格是 X 元。 Bob 很想知道为了买这个礼物他的哪些硬币是必须被使用的，即 Bob 必须放弃收集好的哪些硬币种类。飞机场不提供找零，只接受恰好 X 元。

时间限制： 1000

内存限制： 262144

输入

第一行包含两个正整数 n 和 x。（1 <= n <= 200, 1 <= x <= 10000)

第二行从小到大为 n 个正整数 a₁, a₂, a₃ … a_n （1 <= a_i <= 10000)

输出

第一行是一个整数，即有多少种硬币是必须被使用的。第二行是这些必须使用的硬币的面值（从小到大排列）。

样例输入

5 18
1 2 3 5 10

样例输出

2
5 10

提示

输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 X元。如果不存在必须被使用的硬币，则第一行输出 0，第二行输出空行。

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

答案：

1. 读取输入，获取硬币的面值和礼物的价格。2. 从面值最大的硬币开始，逐步尝试使用硬币组合支付礼物价格。3. 如果当前硬币组合能够恰好支付礼物价格，则记录必须使用的硬币种类，并结束循环。4. 如果无法恰好支付礼物价格，则尝试使用下一个面值的硬币。5. 输出必须使用的硬币种类和数量。

解析：

【喵呜刷题小喵解析】：
本题是一道典型的贪心算法问题，要求找出能够恰好支付礼物价格的硬币组合。由于硬币的面值已经按照从小到大的顺序给出，因此我们可以从面值最大的硬币开始，逐步尝试使用硬币组合支付礼物价格。

具体的算法如下：

1. 从面值最大的硬币开始，依次尝试将其加入当前硬币组合中，判断当前硬币组合是否能够恰好支付礼物价格。
2. 如果当前硬币组合能够恰好支付礼物价格，则记录必须使用的硬币种类，并结束循环。
3. 如果无法恰好支付礼物价格，则尝试使用下一个面值的硬币，重复步骤1和2。
4. 如果所有硬币都无法恰好支付礼物价格，则说明不存在必须使用的硬币，输出0和空行。

在算法实现中，我们可以使用一个变量记录当前硬币组合的面值总和，初始值为0。然后，从面值最大的硬币开始，依次将其加入当前硬币组合中，更新硬币组合的面值总和。如果当前硬币组合能够恰好支付礼物价格，则记录必须使用的硬币种类，并结束循环。如果无法恰好支付礼物价格，则继续尝试下一个面值的硬币。

需要注意的是，由于硬币的面值已经按照从小到大的顺序给出，因此我们可以直接使用贪心算法来解决问题。如果硬币的面值不是按照从小到大的顺序给出，则需要进行排序操作，否则可能会导致算法出错。

创作类型：

原创

本文链接：硬币（2024.3四级）宇航员 Bob 有一天来到火星上，他有收集硬币的习惯。于是他将火星上所

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

分享考题

答案：

解析：

最热门资讯

JAVA工程师面试指导--猎头内部资料

常见面试问题100问！