题目描述

有n种不同面值的硬币，每种面值的硬币都有无限多个。

带尽量少的硬币，并且要能组合出1到m之间（包含1和m）的所有面值。

题目分析

将题目中的硬币面值设为 $a_1, a_2, a_3 … a_n$

首先需要了解一个性质：那就是必须要有面值1，因为1只能被1表示；

然后我们采取贪心的思路：当可以选择大面值的纸币时优先选择大面值

假设$a_1, a_2, a_3 … a_n$为已经排好序的硬币面值

其中$a_i和a_{i+1}$是相邻的两个面值

当我们可以表示$1…a_{i}-1$范围时，我们接下来会优先选择面值$a_i$，同时我们需要选择足够数量的$a_i$面值将可表示范围扩大到$a_{i+1} - 1$,即$a_i - 1 + k * a_i >= a_{i+1} - 1$,其中$k$为$a_i$的选择硬币数量

为了方便循环计算，我们将能够表示价值的最大范围表示为$1…s$,即$1 … a_i - 1$ 表示为 $1 … s$

通过计算可得出$a_i$的硬币数量$k$为$k >= (a_{i+1} - s - 1) / a_i$

代码示例

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 110;

int c[N];
int n, m;

int main()
{
    scanf("%d%d", &m, &n);
    for(int i = 0; i < n; i++) scanf("%d", &c[i]);
    sort(c, c + n); //从小到大排序硬币
    while(n > 0 && c[n - 1] > m) n--; //大于最大面值的硬币不需要

    c[n] = m + 1; 
    //最终一次凑出1 ~ a(i+1)-1, 即最后a(i+1)-1的值为m，由于当i循环到n-1时,我们需要用到i+1=n求解ai的k,所以为了保证计算过程的统一性和边界问题，令c[n] = m + 1

    if(c[0] != 1) puts("-1"); //必须要有1
    else
    {
        int res = 0;
        for(int i = 0, s = 0; i < n; i++) //s为硬币数量
        {
            int k = (c[i + 1] - 1 - s + c[i] - 1) / c[i]; //利用公式上取整
            res += k;
            s += k * c[i]; //扩大表示范围
        }
        cout<<res<<endl;
    }
    return 0;
}