21 Days Training // Day (8 2/3)~(9 2/3)

B. Search and Delete

Notice that the sequence keeps non-decreasing after an operation, we can use map to record every number\’s count.
For every operation, decrease this number\’s count by 1.
After all operations, output all numbers accroding to their counts.
Since the keys in map is sorted well, you can directly output them.
Code :

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

int main() {
    int N, M;cin >> N >> M;
    map<int, int> cnt;
    for (int i=0;i<N;i++) {
        int X;cin >> X;
        if (cnt.find(X)==cnt.end()) cnt[X]=0;
        cnt[X]++;
    }
    for (int i=0;i<M;i++) {
        int X;cin >> X;
        if (cnt.find(X)!=cnt.end()) cnt[X]--;
    }
    for (map<int, int>::iterator it=cnt.begin();it!=cnt.end();it++) {
        for (int i=0;i<(*it).second;i++) cout << it->first << &#039; &#039;;
    }
    return 0;
}