题解：AT_abc448_c [ABC448C] Except and Min

LJQ0808 · 2026-03-10 10:26:27 · 题解

传送门

题解

对于每个查询，我们暂时移除指定的球，然后找最小值，最后再把球放回去。

关键是要高效地找到最小值。如果我们每次都对所有球排序，那复杂度太高了（每次查询需要 O(n \log n) 的复杂度）。

那么使用 multiset 是个好选择：

• multiset 自动保持元素有序。
• 插入和删除都是 O(\log n) 的复杂度。
• 获取最小值（第一个元素）是 O(1) 的复杂度。
• 可以处理重复值（普通 set 不行）。

AC code:

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
signed main(){
    //HAPPY!
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    vector<int> a(n+1);
    multiset<int> s;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s.insert(a[i]);
    }
    while(q--){
        int k;
        cin>>k;
        vector<int> b(k),val(k);
        for(int i=0;i<k;i++){
            cin>>b[i];
            val[i]=a[b[i]];
            s.erase(s.find(val[i]));
        }
        cout<<*s.begin()<<"\n";
        for(int i=0;i<k;i++){
            s.insert(val[i]);
        }
    }
    return 0;
}