No.50 おもちゃ箱

No.50 おもちゃ箱 - yukicoder

• 数が少ないので全探索で ok。 c++ なら next_permutaion が使える。
• 全然関係ないけど yukicoder は自分の解いた問題に色がつくんでなんか達成感があるな。

class ToyBox {
public:
    void solve(void) {
            int N, M;
            cin>>N;
            vector<int> A(N);
            REP(i,N)
                cin>>A[i];
            cin>>M;
            vector<int> B(M);
            REP(i,M)
                cin>>B[i];

            // N が小さいので全探索で間に合う
            sort(RANGE(A));

            int ans = (1<<30);
            // 同じ数の箱を用意するなら容量のおきいものの方がよいので
            // 容量が大きいもの順に並べておく
            sort(RANGE(B));
            reverse(RANGE(B));

            do {
                auto box = B;
                int i = 0;
                int j = 0;
                bool ok = true;
                while (true)
                {
                    if (A[i] > box[j])
                        ++j;
                    if (j == M || A[i] > box[j])
                    {
                        ok = false;
                        break;
                    }
                    box[j] -= A[i];
                    ++i;
                    if (i == N)
                        break;
                }
                if (ok)
                    ans = min(ans, j+1);
            } while (next_permutation(RANGE(A)));
            if (ans > M)
                ans = -1;
            cout<<ans<<endl;
    }
};