栈、队列、优先队列和题目讲解

104 阅读 0 评论 69 点赞

我是靠谱客的博主开朗小刺猬，这篇文章主要介绍栈、队列、优先队列和题目讲解，现在分享给大家，希望可以做个参考。

训练题目网址（密码hpuacm）：https://cn.vjudge.net/contest/241502#overview

栈和队列的基础知识不再讲解，参考之前写的博客

栈：https://blog.csdn.net/hpu2022/article/details/79845577

队列：https://blog.csdn.net/hpu2022/article/details/79845564

这里着重讲一下优先队列：

优先队列出的顺序是按照自己设置的优先等级来出队列的，如果自己不设置优先级的话，默认优先级为越大优先级越高。

定义方法：priority_queue <int> que;

如果想自己决定优先级可以这样写：

priority_queue <int, vector <int>, greater <int> > que; 这样写是升序，即值越小优先级越高

priority_queue <int, vector <int>, less <int> > que; 这样写是降序，即值越大优先级越高

对于结构体类型的队列定义，以及设置优先级模板参考如下代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
struct node{
	int pri;
	int id;
};
// 排序依据是pri的值越小优先级越高，pri相同则id越小越在前。
bool operator<( const node &a, const node &b )
{
	if( a.pri == b.pri )
		return a.id > b.id;
	return a.pri > b.pri;
}
priority_queue<node> que;
// 注意：这里是从大到小排列的，但是输出的时候是从小到大排列的。

A题思路：先说说题意，大概就是一个人走在一条路上，会遇到很多石头，每个石头都有两个属性，位置和能够被扔出去的距离，越重能被仍出去的距离越小。第奇数次遇到石头就扔出去，偶数次不管，等这个人的前方已经没有石头了问这个人已经走了多远。其实就是问最后一个石头的位置。

定义一个优先队列，然后将每次要被扔的石头临时存下来，然后修改一下数据，和被扔完之后的一样，然后重新放入队列。

B题思路：定义一个优先队列，让队列中始终只有k个元素，每次判断新输入的元素，如果大于队顶的元素就入队，否则忽略。这样就能保证队列里最小的元素就是第k大的元素。

C题思路：因为有三个医生，并且每个病人以及每次询问都会指定一个医生，所以可以定义三个优先队列，用来存储三个医生的看病情况。

D题思路：就是给你一列数，问能不能按指定的顺序输出，参考代码如下

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	string in;
	string out;
	stack<char> s;
	vector<int> ve;

	while( cin >> n )
	{
		while( s.size() ) s.pop();
		ve.clear();
		cin>>in>>out;
		int index = 0;
		for( int i=0, j=0; i<out.size(); i++ )
		{
			s.push(in[index++]);
			ve.push_back(0);	// 0进1出
			if( s.top() == out[j] )
			{
				while( true )
				{
					s.pop();
					ve.push_back(1);
					j++;
					if( s.empty() ||  j >= out.size() || s.top() != out[j] )
						break;
				}
			}
		}
		if( s.empty() )
		{
			printf("Yes.n");
			for( int i=0; i<ve.size(); i++ )
				if( ve[i] == 0 )
					printf("inn");
				else if( ve[i] == 1 )
					printf("outn");

			printf("FINISHn");
		}
		else
		{
			printf("No.n");
			printf("FINISHn");
		}
	}
	
	return 0;
}