锐客网

  1. 首页 > it技术 > >

Code|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

【Code|Code Forces－681C（模拟题，优先队列，设计STL）】Output
6 insert 1 insert 1 removeMin removeMin insert 2 getMin 2

代码分析
#include//包含C++的所有头文件 using namespace std; char str[10]; //存放所输入的命令 int i, j, n, t, x; pair p[1000010]; //对于pair类，由于它只有两个元素，分别名为first和second，可直接使用 普通的点操作符即可访问其成员 priority_queue , greater > 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()

    推荐阅读


    上一篇：一个人的旅行，一个人的生活，一个人的一辈子。2019中国单身人数已超过2亿。

    下一篇：寒假作业秀——老照片里的故事