ABC 366 C Balls and Bag Query Solution

· · 题解

Atcoder Beginner Contest 366 Problem C.

Balls and Bag Query \,\,\,\, Solution

还是 STL 大法好用。

很明显，这一题可以使用 STL_MAP 完成。总共有 2 \times 10^5 种球，也不会 MLE。

我们建立 int 对 int 的 map，第一个值表示球的编号，第二个值表示球的数量。

对于第一问，可以直接读入 x ，随后更改 map 当中的值即可。

对于第二问，访问 map 当中的 x，由于题目当中已经保证了 x 已经存在，只需要 map_x 减去 1 即可。

对于第三问，无需 O(n) 查找，在输入时判断是否为新的值，在输出时判断 map_x 是否被拿空，O(1) 维护即可。

评测结果：AC，193ms

代码如下，码风良好：

#include <bits/stdc++.h>
using namespace std;
int q,op,x,tp = 0;
map <int, int> mp;
int main(){
    cin >> q;
    while(q--){
        cin >> op;
        if(op == 1){
            cin >> x;
            if(mp[x] == 0) tp++;
            mp[x]++;
        }else if(op == 2){
            cin >> x;
            if(mp[x] == 1) tp--;
            mp[x]--;
        }else{
            cout << tp << endl;
        }
    }


    return 0;
}