贪心:购物:硬币凑值(最少)

简介: 题目描述:你就要去购物了,现在你手上有N种不同面值的硬币,每种硬币有无限多个。为了方便购物,你希望带尽量少的硬币,但要能组合出1到X之间的任意值。

题目描述:

你就要去购物了,现在你手上有N种不同面值的硬币,每种硬币有无限多个。为了方便购物,你希望带尽量少的硬币,但要能组合出1到X之间的任意值。

输入格式:

第一行两个数X、N,以下N个数,表示每种硬币的面值。

【数据规模】

对于30%的数据,满足N≤3,X≤20;

对于100%的数据,满足N≤10,X≤1000.

输出格式:

最少需要携带的硬币个数,如果无解输出-1.

输入输出样例

输入 #1复制

20 4

1 2 5 10

输出:

5

分析:这道题我是真没听懂,但是能够记得其中的步骤是怎样写的。

include<bits/stdc++.h>

using namespace std;

int cmp(long long a,long long b)//这个函数就很,,,

{

return a>b;

}

int main(void)

{

long long n,x;
cin>>x>>n;
long long arr[n],ans=0,now=0;
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr,arr+n,cmp);//这是进行排序的函数,sort默认,后面加一个cmp自定义函数,使他倒叙。
for(int i=1;i<=x;i++)//从1开始遍历,看能不能凑出硬币
{
for(int j=0;j<n;j++)//遍历数组,从大往小找;
    {
if(i-arr[j]>=0)//这个判断条件很关键;
        {
            ans++;
            now=now+arr[j];
            i=now;
break;
        }
    }
}
cout<<ans;
return 0;

}

目录
相关文章
|
程序员 C语言
C语言设计三子棋
C语言设计三子棋
|
机器学习/深度学习 并行计算 Java
【java】 vector api 快速入门
【java】 vector api 快速入门
1140 0
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
167 0
|
消息中间件 缓存 运维
Java 线程池 8 大拒绝策略,面试必问!
Java 线程池 8 大拒绝策略,面试必问!
285 0
Java 线程池 8 大拒绝策略,面试必问!
|
Java 程序员
一个多线程死锁案例,如何避免及解决死锁问题?
​ 多线程死锁在java程序员笔试的时候时有遇见,死锁概念在之前的文章有介绍,大家应该也都明白它的概念,不清楚的去翻看历史文章吧。 下面是一个多线程死锁的例子 输出 thread1 get lock1 thread2 get lock2 两个线程相互得到锁1,锁2,然后线程1等待线程2释放锁2,线程2等待线程1释放锁1,两者各不相互,这样形成死锁。
1175 0
趣味题:100枚硬币
1、桌子上堆放有 100 枚硬币,每个都有正面和反面。其中 10 个正面朝上,90 个反面朝上。你无法通过感觉、视觉或任何其他方法知道硬币的哪一面朝上。请你将它们分成 2 堆,每一堆正面朝上的硬币数量必须相同。 答:随机摸十枚出来,然后把它们翻面 这样子无论如何,这10枚里面正面朝上的数目都
5155 0