Code Forces－681C（模拟题，优先队列，设计STL）

题目大意

其实就是用有限队列模拟一个类似..的。。。其实就是模拟题目所述过程

insert x

将值为x的元素放在堆中;（直接插入元素）

getMin x

堆中包含的最小元素的值等于x;（这个x是不是对应的值。如果队列中首元素比其大，那就加其上一个；如果相等直接取出；如果小于就不断取队列中最小元素。）

removeMin

从堆中提取最小元素（只有一个实例，如果有多个）。（要先判队列内元素是否为空）
注意判断命令的先后顺序就是了

输入输出分析

Input

2
insert 3         //插入3
getMin 4       //4>3，就要插入4；

Output

4
insert 3
removeMin
insert 4
getMin 4

Input

4
insert 1       //插入1
insert 1       //插入1
removeMin  //此时最小为1
getMin 2   

Output

6
insert 1
insert 1
removeMin
removeMin
insert 2
getMin 2

代码分析

#include<bits/stdc++.h>     //包含C++的所有头文件 
using namespace std;

char str[10]; //存放所输入的命令
int i, j, n, t, x;
pair<int, int> p[1000010];  //对于pair类，由于它只有两个元素，分别名为first和second，可直接使用
普通的点操作符即可访问其成员
priority_queue <int, vector<int>, greater<int> > q;  
//第二个参数为容器类型。第二个参数为比较函数。

int main()
{
    scanf("%d",&n);
    for(i = 1; i <= n; i++)
    {
        scanf("%s", str); //输入
        if(str[0] != 'r') scanf("%d",&x); //判断如果不是removMin就继续输入
        if(str[0] == 'i') // insert
        {
            q.push(x); //插入数字
            p[++t] = make_pair(1,x); //make_pair对已存在的两个数据构造一个新的pair类型
        }
        else if(str[0]=='r') //removMin
        {
            if(q.empty()) //如果数组为空
            {
                p[++t] = make_pair(1,1);
                q.push(1); //压入
            }
            q.pop(); //非空，弹出顶端元素
            p[++t] = make_pair(2,0); //压入
        }
        else //getMin
        {
            while(!q.empty() && q.top()<x)
            {
                q.pop();
                p[++t] = make_pair(2,0);
            }
            if(q.empty() || q.top() != x)
            {
                q.push(x);
                p[++t] = make_pair(1, x);
            }
            p[++t] = make_pair(3, x);
        }
    }
    printf("%d\n", t);

    for(i = 1; i <= t; i++)
    {
        if(p[i].first == 1)
            printf("insert %d\n", p[i].second);
        else if(p[i].first == 2)
            printf("removeMin\n");
        else
            printf("getMin %d\n", p[i].second);
    }
    return 0;
}