题目描述

用硬币$a_1, …, a_n$ 凑出$[1, m]$.

算法1

$O(n)$

每次尽量扩展当前区间$[1, R]$. 然后是的当前区间至少能涵盖$[1, a_i - 1]$。
因为这样的话，下次就能用$a_i$了。

C++ 代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;


int a[110];
int main() {
    int m, n;
    cin >> m >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a, a + n);
    while (n > 0 && a[n - 1] > m) n --;
    a[n] = m + 1;

    int cur = 0;
    int result = 0;
    // cur + a[pos] * k >= a[pos + 1] - 1
    // k >= ceil(min(a[pos + 1], m) - cur) / a[pos]

    for (int i = 0; i < n; ++i) {
        int k = ceil((a[i + 1] - 1 - cur) * 1.0 / a[i]);
        cur += k * a[i];
        result += k;
    }
    cout << result << endl;
}