codeforces1620D Exact Change（贪心/枚举）

题目链接：codeforces1 1620D

题目思路：

根据贪心思想，先满足最大的那个数至多需要的面值为 $3$ 的硬币数 $cur$，然后再枚举面值为 $1$ 和 $2$ 的硬币数是否有可行解，答案取最小值即可。

参考代码：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
void solver() {
   
    ll n; cin >> n;
    vector<ll> a(n);
    for (ll &i:a) cin >> i;
    sort(a.begin(), a.end());
    int ans = 0x3f3f3f3f;
    int cur = a.back() / 3;
    for (int one = 0; one <= 2; one++) {
   
        for (int two = 0; two <= 2; two++) {
   
            for (int three = max(0, cur-2); three <= cur; three++) {
   
                int coins = one + two + three;
                if (coins >= ans) continue;
                bool flag = true;
                for (ll num : a) {
   
                    bool isok = false;
                    for (int i = 0; i <= one; i++) {
   
                        for (int j = 0; j <= two; j++) {
   
                        	ll last = num - i - j*2;
                            if (last >= 0 && last % 3 == 0 && last / 3 <= three) {
   
                                isok = true;
                                break;
                            }
                        }
                    }
                    if (!isok) {
   
                        flag = false;
                        break;
                    }
                }
                if (flag) ans = coins;
            }
        }
    }
    cout << ans << '\n';
}
int main(){
   
    int _;
    cin >> _;
    while (_--) {
   
        solver();
    }
    return 0;
}