CODE FESTIVAL 2017 qual B B - Problem Set (4Q, 茶色, 200 点)

素朴な map の練習問題

• 問題へのリンク

問題概要

りんごさんは 個の問題案を持っており、 個目の問題案の難易度は である。

ここから、配点が であるような 問からなる問題セットを作ることは可能か？

制約

• 
• 

考えたこと

連想配列 (C++ ならば map) の練習問題。次のような連想配列を用意しよう。

---

• problems[x]：残っている問題案の中に、配点 の問題は何問あるか？

---

そうして、 に対して、problems[T[i]] の値を 1 減らしていけば良い。途中で負の値になったら不可能だとわかる。

計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M, D, T;
    cin >> N;
    map<int, int> problems;
    for (int i = 0; i < N; i++) {
        cin >> D;
        problems[D]++;
    }

    cin >> M;
    bool res = true;
    for (int i = 0; i < M; i++) {
        cin >> T;
        problems[T]--;
        if (problems[T] < 0) res = false;
    }
    cout << (res ? "YES" : "NO") << endl;
}