CodeForces - 681C 【优先队列】

传送门
优先队列在语法(推入,删除)上与普通队列一样,不同在于声明时要这样：priority_queue<int,vector<int>,greater<int> >q;
优先队列中默认出来的top值为该队列中的最小的数.这道题就是一道模拟优先队列的题.(被人看来是水题,而我却。)
代码如下：

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=1000005;
struct node
{
    char ch;
    int x;
}op[maxn];

int main()
{
    priority_queue<int,vector<int>,greater<int> >q;//优先队列的严格声明方式.
    int n,i,k=0,u;//默认该队列中最小的数为优先级最高的数,即q.top=q.min.
    char s[10];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s",s);
        if(s[0]=='i')
        {
            scanf("%d",&u);
            op[k].x=u;
            op[k++].ch='i';
            q.push(u);
        }
        else if(s[0]=='r')
        {
            if(q.empty()){//防止队列为空时,该操作非法;
                op[k].x=0;
                op[k++].ch='i';
                q.push(0);
            }
            q.pop();
            op[k++].ch='r';
        }
        else{
            scanf("%d",&u);//u就是目标数.
            if(!q.empty()&&q.top()==u)
            {
                op[k].x=u;
                op[k++].ch='g';
            }
            else if(!q.empty()&&q.top()>u)
            {
                op[k].x=u;
                op[k++].ch='i';
                q.push(u);
                op[k].x=u;
                op[k++].ch='g';
            }
            else{
                while(!q.empty()&&q.top()<u)//删到队列中最小的数小于目标数为止.
                {
                    op[k].x=q.top();
                    op[k++].ch='r';
                    q.pop();
                }
                if(!q.empty()&&q.top()>u || q.empty())
                {
                    op[k].x=u;
                    op[k++].ch='i';
                    q.push(u);
                }
                op[k].x=u;
                op[k++].ch='g';
            }
        }
    }
    printf("%d\n",k);//总共最少步骤
    for(int i=0;i<k;i++)
    {
        if(op[i].ch=='i')
            printf("insert %d\n",op[i].x);
        else if(op[i].ch=='r')
            printf("removeMin\n");
        else
            printf("getMin %d\n",op[i].x);
    }
}