题目描述

此题的思路明面上很简单，用最少的硬币数量凑出1-m之间的所有的面值。

此题的解法步骤可以分为以下几部分：

1、需要对所有面值进行排序，并且删除末尾大于m的所有面额，并且补上m + 1,因为大于m的硬币肯定不会用，第二加上m + 1的是为了避免边界条件，让我们的解算思路贯彻下去，就是我们需要凑齐a(i) - 1之间的所有面值。如果不加的话也可以，不过最后一个就是求最后一次凑齐的面额与最终需要的m之间需要多少最大的面额数。

2、第二步就是经典的求解每一个面值硬币需要的数量了，假如说前面凑齐的总面额为s，那么要凑齐面额a(i+1)-1需要多少的数量，k = (a(i+1) - 1 -s) / a(i)上取整。

3、此处我觉得最好需要判断k值是否为负值，但是发现不判断也可以，不知道有没有大佬能解释下。

算法1

(排序 加 遍历) $O(nlogn)$

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> input(m, 0);

    for(int i = 0; i < m; i ++ ) cin >> input[i];

    sort(input.begin(), input.end());

    if(input[0] != 1) cout << -1 << endl;
    else
    {
        while(m > 0 && input[m - 1] > n) m -- ;
        input[m] = n + 1;
        int res = 0;
        for(int i = 0, s = 0; i < m; i ++ )
        {
            int k = (input[i + 1] - 1 - s + input[i] - 1) / input[i];
            res += k;
            s += input[i] * k;
        }
        cout << res << endl;
    }


    return 0;
}