首页 > 代码库 > 【STL】优先队列priority_queue详解+OpenJudge-4980拯救行动

【STL】优先队列priority_queue详解+OpenJudge-4980拯救行动

2024-08-20 08:13:17   252人阅读

一、关于优先队列

队列（queue）这种东西广大OIer应该都不陌生，或者说，队列都不会你还学个卵啊(╯‵□′)╯︵┻━┻咳咳，通俗讲，队列是一种只允许从前端（队头）删除元素、从后端（队尾）插入元素的数据结构。而优先队列（priority queue）是一种赋予每个队列中元素以一个优先级的队列。在执行删除操作时，优先队列会删除具有最高优先级的元素。如此奇妙的优先队列有什么用呢，举个例子，给定一个长为n的序列和m组询问，对于每组询问，我们要找出删去序列中最小的数，再向序列加入一个数。朴素的想法是对每个询问从头到尾扫一遍，找出最小值，时间复杂度为O(nm)。而优先队列可以将时间复杂度降低到O(nlgn)的级别。那它是怎么做到的呢？其实，优先队列（又称堆）是一颗完全二叉树，其每个子节点与父节点间都具有某种特性（即为我们规定的优先级）。二叉树的性质决定了优先队列删除操作O(lgn)的复杂度。

二、STL之priority_queue

优先队列好用归好用，然而，它不好写_(:з」∠)_但是，STL（Standard Template Library 标准模板库）里给出了优先队列的模板~\(≧▽≦)/~

priority_queue定义在头文件<queue>里，和普通队列一样，priority_queue拥有如下操作：

1、priority_queue<Type, Container, Functional>Q：创建一个新的优先队列Q，其Type为其数据类型，Container 为保存数据的容器，Functional 为元素比较方式；

　　特别说明：Container必须是用数组实现的容器，默认为vector；Functional默认为operator <。所以如果我们把Container和Functional都缺省，优先队列就是一个队头元素最大的大根堆。

2、Q.top()：返回队头元素；

3、Q.pop()：删除队列头部元素；

4、Q.push(x)：在队尾增加元素x；

5、Q.empty()：判断队列是否为空（如果队列为空则返回true，否则，返回false）；

6、Q.size()：返回队列中元素个数。

三、OpenJudge-4980拯救行动题解

描述

公主被恶人抓走，被关押在牢房的某个地方。牢房用N*M (N, M <= 200)的矩阵来表示。矩阵中的每项可以代表道路（@）、墙壁（#）、和守卫（x）。 
英勇的骑士（r）决定孤身一人去拯救公主（a）。我们假设拯救成功的表示是“骑士到达了公主所在的位置”。由于在通往公主所在位置的道路中可能遇到守卫，骑士一旦遇到守卫，必须杀死守卫才能继续前进。 
现假设骑士可以向上、下、左、右四个方向移动，每移动一个位置需要1个单位时间，杀死一个守卫需要花费额外的1个单位时间。同时假设骑士足够强壮，有能力杀死所有的守卫。

给定牢房矩阵，公主、骑士和守卫在矩阵中的位置，请你计算拯救行动成功需要花费最短时间。

输入

第一行为一个整数S，表示输入的数据的组数（多组输入）
随后有S组数据，每组数据按如下格式输入 
1、两个整数代表N和M, (N, M <= 200). 
2、随后N行，每行有M个字符。"@"代表道路，"a"代表公主，"r"代表骑士，"x"代表守卫, "#"代表墙壁。

输出

如果拯救行动成功，输出一个整数，表示行动的最短时间。
如果不可能成功，输出"Impossible"

原题链接→_→OpenJudge-4980拯救行动

读了题我们发现，这就是一个宽搜嘛。我们只要以时间定义优先级，把每个点能拓展的状态放入优先队列处理就可以了。

愉快的贴上代码：

技术分享 
 1 #include<cstdio>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAXL=210;
 6 int dir[]={-1,1,0,0},dir_[]={0,0,-1,1};
 7 int s;
 8 int n,m;
 9 int map[MAXL][MAXL];
10 bool vis[MAXL][MAXL];
11 int dx,dy;
12 struct node 
13 {
14     int x,y,time;
15     friend bool operator < (node A,node B){return A.time>B.time;}
16     //重载 < ，定义时间为优先级，时间小的元素置于队首
17 };
18 priority_queue <node> q;//priority_queue <node,vector<node>,operator <> q; 
19 int main()
20 {
21     scanf("%d",&s);
22     while(s--)
23     {
24         while(!q.empty())q.pop();//清空队列q，注意：没有q.clear()的用法 
25         memset(vis,false,sizeof(vis));
26         memset(map,0,sizeof(map));
27         scanf("%d%d",&n,&m);
28         for(int i=1;i<=n;++i)
29         {
30             char c[MAXL];
31             scanf("%s",c);
32             for(int j=0;j<m;++j)
33             {
34                 if(c[j]==‘a‘)dx=i,dy=j+1;
35                 else if(c[j]==‘r‘)q.push((node){i,j+1,0}),vis[i][j+1]=true;
36                 else if(c[j]==‘x‘)map[i][j+1]=1;//1代表守卫 
37                 else if(c[j]==‘#‘)map[i][j+1]=2;//2代表墙壁 
38             }
39         }
40         while(!q.empty())
41         {
42             int x=q.top().x,y=q.top().y,time=q.top().time;
43             if(x==dx&&y==dy)break;
44             for(int i=0;i<4;++i)
45             {
46                 if(x+dir[i]<1||x+dir[i]>n||y+dir_[i]<1||y+dir_[i]>m)continue;
47                 if(vis[x+dir[i]][y+dir_[i]]||map[x+dir[i]][y+dir_[i]]==2)continue;
48                 vis[x+dir[i]][y+dir_[i]]=true;
49                 if(map[x+dir[i]][y+dir_[i]]==0)q.push((node){x+dir[i],y+dir_[i],time+1});
50                 else if(map[x+dir[i]][y+dir_[i]]==1)q.push((node){x+dir[i],y+dir_[i],time+2});
51             }
52             q.pop();
53         }
54         if(q.empty())printf("Impossible");
55         else printf("%d",q.top().time);
56         printf("\n");
57     }
58     return 0;
59 }
OpenJudge-4980拯救行动

弱弱地说一句，本蒟蒻码字也不容易，转载请注明出处http://www.cnblogs.com/Maki-Nishikino/p/6056072.html

【STL】优先队列priority_queue详解+OpenJudge-4980拯救行动


联系
我们