Yukicoder050 おもちゃ箱

問題概要

サイズ$a[i]$のおもちゃが$N$個、サイズ$b[i]$のおもちゃ箱が$B$個ある。 おもちゃを全て収納するのに必要な最初のおもちゃ箱の数を答えよ。

$N,M\leqq10$、$A[i],B[i]\leqq20$

yukicoder050

解法

$a,b$を整頓して、$O(N!M)$だけ試せば良い。
問題文におもちゃって書かれていすぎて、おもちゃゲシュタルト崩壊した

計算量:$O(N!M)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    #define ALL(a)  begin((a)),end((a))
    #define RALL(a) (a).rbegin(), (a).rend()
    #define SZ(a) int((a).size())
    #define SORT(c) sort(ALL((c)))
    #define RSORT(c) sort(RALL((c)))
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    const int INF = 1e9;
    
    
    LL N;
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
        VI a(N);
        for (int &x : a) {
            cin >> x;
        }
        int M; cin >> M;
        VI b(M);
        for (int &x : b) {
            cin >> x;
        }
        RSORT(b);
        SORT(a);
        int ans = INF;
        do {
            VI B = b;
            int id = 0;
            map<int, int>Map;//使ったidを管理
            int acnt = 0;
            FOR(i, 0, N) {
                if (id >= M) {
                    id = INF;
                    continue;
                }
                while (B[id] < a[i]) {
                    id++;
                }
                if (id < M && B[id] >= a[i]) {
                    B[id] -= a[i];
                    acnt++;
                    Map[id] = 1;
                    if (B[id] == 0)id++;
                }
            }
    
            if (acnt == N && id != INF)
                ans = min(ans, SZ(Map));
    
        } while (next_permutation(ALL(a)));
        if (ans == INF)ans = -1;
        cout << ans << "\n";
    
        return 0;
    }