超级麻烦的算法

· · 题解

优先队列与动态数组！

首先我们看到了第三种操作，需要我们输出最大的数的最早的插入位置。最大我们不免想到可以用优先队列也就是堆，最早又可以想到动态数组 vector，所以我们就可以得出两者相结合的方法完成第三种操作。

之后第二种操作就显得简单了许多，大家都知道队列的特点是先进先出，正好可以做到把先插入的先删除。

十分详细的代码：

#include<bits/stdc++.h>
using namespace std;
queue<int> q1;
priority_queue<int> q2;
vector<int> v[1000005];
int a[1000005],vis[1000005],cnt;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int op;
        cin>>op;
        if(op==1) {
            int m;
            cin>>m;
            a[++cnt]=m;
            q1.push(cnt);
            q2.push(m);
            v[m].push_back(cnt);
            //存储所有要用到的数据 
        }
        else if(op==2) {
            while(vis[q1.front()]) q1.pop();
            //删除已经使用过的数据 
            vis[q1.front()]=1;
            cout<<q1.front()<<" ";
            q1.pop();
        }
        else{
            while(vis[v[q2.top()][0]]) v[q2.top()].erase(v[q2.top()].begin()),q2.pop();
            //对于一个值找到他最早的插入时间，依然将使用过的先删除 
            vis[v[q2.top()][0]]=1;
            cout<<v[q2.top()][0]<<" ";
            v[q2.top()].erase(v[q2.top()].begin());
            //vector的erase函数中填入的是元素地址 
            q2.pop();
        }
    } 
    return 0;
}