洛谷P1658 购物

题目戳

题目描述

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

输入输出格式

输入格式：

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

【数据规模】

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

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

输出格式：

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

输入输出样例

输入样例#1：

20 4
1 2 5 10

输出样例#1：

5

Solution：

一开始直接额考虑dp，以为是DAG上的DP，但是发现题意是1到x的所有值都要组成，而我开始的dp是固定终点的，So放弃。我们来考虑一下贪心：没有面额为1的直接输出-1，否则就取当前能取的最大值。什么意思呢？举个例子假设1、3、5，要组成10的面额，开始值为0，所以取1  ->  然后组成最大值为1，为了组成2，还是要取1  ->  最大值为2，此时大于等于面额3的硬币-1，所以选3  -> 此时最大值为5 ，大于等于5的面额-1 ->最大值变为了10，等于x，结束。。所以举的例子最少选4个硬币。为什么这样可行呢？因为小的面额必须先组成1到大面额的值-1的所有值(比如需要两个1来组成1、2)，再去选大面额，这样大于大面额的值就以大面额为底加上小面额(比如以3为底，与两个1可以组成4、5)组成的最大值与下一个大面额的值-1比较，如果小于则再选一次刚刚的面额，直到大于等于为止便选当前的这个大面额，重复前面步骤，直到能组成的面额大于等于x停止。多举例子模拟理解，不难证明这样贪心是正确的且能保证硬币个数最小。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define inf 233333333
int x,n,a[1005],sum,ans;
bool bj[100005];
int main()
{
    //freopen("shopping.in","r",stdin);
    //freopen("shopping.out","w",stdout);
    scanf("%d%d",&x,&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),bj[a[i]]=1;
    sort(a+1,a+n+1);
    if(!bj[1])cout<<-1;
    else {
    while(sum<x)
    {
        for(int i=n;i>=1;i--)
        if(sum+1>=a[i]){sum+=a[i],ans++;break;} 
    }
    cout<<ans;
    }
    return 0;
}