题解：AT_abc448_c [ABC448C] Except and Min

New_Void · 2026-03-10 22:15:12 · 题解

AT_abc448_c [ABC448C] Except and Min

思路

注意到 k 的值很小，所以可以暴力取出每个 a_{b_i} 的物品，考虑要算出取出这些球的最小值，那我们不难想到可以用一个小根堆维护初始序列的最小值，然后对要取出的这 k 个物品的权排序，若这个物品的权等于这个当前堆的堆顶，那么就把堆顶弹掉，否则的话就不做，因为只考虑最小值，而这个数若不是最小值的话定然不会影响答案。然后用一个数组记录被弹掉的值，最后再放回去即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;
int a[N],b[10],c[10];
priority_queue<int,vector<int>,greater<int> > q;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,Q;cin>>n>>Q;
    for (int i=1;i<=n;i++) cin>>a[i],q.push(a[i]);
    while (Q--){
        int k;cin>>k;
        vector<int> v;
        for (int i=1;i<=k;i++) cin>>b[i];
        for (int i=1;i<=k;i++) c[i]=a[b[i]];
        sort(c+1,c+1+k);
        for (int i=1;i<=k;i++){
            if (c[i]==q.top()) q.pop(),v.push_back(c[i]);
        }
        cout<<q.top()<<'\n';
        for (int i=0;i<(int)v.size();i++) q.push(v[i]);
    }
    return 0;
}