P2001 硬币的面值

    • 29通过
    • 232提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 洛谷原创
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小A有n枚硬币,现在要买一样不超过m元的商品,他不想得到找钱(多脏啊),同时又不想带太多的硬币,且硬币可以重复,现在已知这n枚硬币的价值,请问最少需要多少硬币就能组合成所有可能的价格?

    输入输出格式

    输入格式:

    第一行两个数:n、m。

    下一行,共n个数字,表示硬币的面值。

    输出格式:

    一行一个数,表示最少需要多少硬币。如果无解请输出“No answer!!!”

    输入输出样例

    输入样例#1: 复制
    5 31
    1 2 8 4 16
    
    输出样例#1: 复制
    5
    

    说明

    【数据范围】

    1<=m<=2000000000,1<=N<=2000000

    只有9、10会卡人,放心贪

    对于20%的数据 1<=n<=10 1<=m<=100

    对于60%的数据 1<=n<=1000 1<=m<=10000

    对于80%的数据 1<=n<=30000 1<=m<=20亿

    对于100%的数据 1<=n<=20万 1<=m<=2^63

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。