题解：AT_abc448_c [ABC448C] Except and Min

· · 题解

模拟题，考察 STL 的使用。

这道题需要使用三个 STL 模板，分别是：map，vector，\operatorname{sort}。

如果对这方面不太了解，可以学习一下这篇文章。

接下来进入正题。

首先，我们能够想到的最朴素的做法肯定是定义一个桶，统计每个数出现的次数。

然后观察到数据范围很大，所以需要用 map。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int n,q,a[300005],k,b[6],minn = 1e9;
map <int,int> mp;
int main(){
    cin >> n >> q;
    for (int i = 1;i < n + 1;i++){
        cin >> a[i];
        mp[a[i]]++;
        minn = min(minn,a[i]);
    }
    while (q--){
        cin >> k;
        for (int i = 0;i < k;i++){
            cin >> b[i];
            mp[a[b[i]]]--;
        }
        if (mp[minn]){
            cout << minn << '\n';
        }
        else{
            int temp = minn;
            while (!mp[temp]){
                temp++;
            }
            cout << temp << '\n';
        }
        for (int i = 0;i < k;i++){
            mp[a[b[i]]]++;
        }
    }
}

这里做了一些小小的优化。先统计所有球上的数中的最小值，如果在取出球之后仍然有不少于 1 个球上的数为这个最小值，就可以直接输出。

否则不断将最小值加一，如果某一个球上的数为这个最小值，则输出。

显然，这样做会超时。

于是考虑优化。

可以发现，比较耗时的部分在于枚举最小值，但并非每个值都在球上出现过。

于是可以定义一个 vector，用来统计哪些数在球上出现过，然后从小到大排序，枚举这个 vector 中的每个数即可，大大降低了时间复杂度。

于是便可通过本题。代码如下：

#include <bits/stdc++.h>
using namespace std;
int n,q,a[300005],k,b[6],minn = 1e9;
map <int,int> mp;
vector <int> v;
int main(){
    cin >> n >> q;
    for (int i = 1;i < n + 1;i++){
        cin >> a[i];
        mp[a[i]]++;
        minn = min(minn,a[i]);
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    while (q--){
        cin >> k;
        for (int i = 0;i < k;i++){
            cin >> b[i];
            mp[a[b[i]]]--;
        }
        if (mp[minn]){
            cout << minn << '\n';
        }
        else{
            int temp = 0;
            while (!mp[v[temp]]){
                temp++;
            }
            cout << v[temp] << '\n';
        }
        for (int i = 0;i < k;i++){
            mp[a[b[i]]]++;
        }
    }
}