c++ priority

前言:

这篇文章是为了帮助一些

像我这样的菜鸟

找到简单的题解

之前说了数据结构队列

本期我们来看一下优先队列

问题描述: 题目描述

依次读入 n 个整数 ai​ ，其中可能存在相同的元素。

对于每次读入的元素 ai​，如果它与前面剩余元素中的最小值相同时，则同时消除这 2 个元素，并输出此次消除操作之后剩余元素的最小值。如果该元素没有发生“消除”操作，则输出 None。

特别地，在 “输出剩余元素的最小值” 时，如果没有剩余元素，则输出 -1 。

输入格式

第一行：n (1≤n≤105) 。

第二行：n 个用空格隔开的整数 ai​ (−109≤ai​≤109) 。

输出格式

输出共 n 行，每行一个操作结果。

样例输入

5
3 1 1 3 3

样例输出

None
None
3
-1
None

问题解析:

本题之需要了解优先队列

然后就非常简单了

优先队列的简介:

优先队列也是一种抽象数据类型。

优先队列中的每个元素都有优先级，

而优先级高（或者低）的将会先出队，

而优先级相同的则按照其在优先队列中的顺序依次出队。

优先队列的函数:

优先队列函数

q.size();	返回q里元素个数
q.empty();	返回q是否为空，空则返回1，否则返回0
q.push(k);	在q的末尾插入k
q.pop();	删掉q的第一个元素
q.top();	返回q的第一个元素

priority_queue队列：相关资料

---

重点:

优先队列定义

分大根堆和小根堆

priority_queue  q;
//也可以是是一个结构体
priority_queue ,greater > q;//从小到大
//不需要#include头文件
priority_queue ,less >q;//从大到小
//默认从大到小

---

题目代码:

先写完变量如题目

需优先队列

priority_queue,greater > q;//从小到大
int n,a,i,x;//如题目

直接进入主函数

int main()
{
	cin>>n;
	while(n--)//这样写简单
	{
		cin>>x;//输入
		if(!q.empty() && x==q.top())//如果出现了一次
		{
			q.pop();//删掉两个数
			if(q.empty()) cout<<-1< 
   完整代码: 
   
#include
using namespace std;
priority_queue,greater > q;//从小到大
int n,a,i,x;//如题目
int main()
{
	cin>>n;
	while(n--)//这样写简单
	{
		cin>>x;//输入
		if(!q.empty() && x==q.top())//如果出现了一次
		{
			q.pop();//删掉两个数
			if(q.empty()) cout<<-1< 
   题目测评: 
   
 
   
 样例通过
 
   
 
   成功AC