优先队列涉及priority_queue函数
它的模板声明带有三个参数，priority_queue<Type, Container, Functional>
Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。
Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list.
STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个
参数缺省的话，优先队列就是大顶堆，队头元素最大。
操作如下
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
int num,l;
bool friend operator < (node a,node b)
{
if (a.num == b.num)
return a.l > b.l;
return a.num < b.num;
}
};
int main()
{
int n;
scanf ("%d",&n);
priority_queue<node> Q;
node a;
for (int i = 1 ; i <= n ; i++)
{
scanf ("%d",&a.num);
a.l = i;
Q.push(a);
}
while (!Q.empty())
{
a = Q.top();
printf ("%d\n",a.num);
Q.pop();
}
return 0;
}
使用注意
读取数据和弹出数据时要判断是否为空
以题为列
Train Problem I
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 18882 Accepted Submission(s): 7099
Problem Description
As the new term comes, the Ignatius Train Station is very busy nowadays. A lot of student want to get back to school by train(because the trains in the Ignatius Train Station is the fastest all over the world ^v^). But here comes a problem, there is only one railway where all the trains stop. So all the trains come in from one side and get out from the other side. For this problem, if train A gets into the railway first, and then train B gets into the railway before train A leaves, train A can't leave until train B leaves. The pictures below figure out the problem. Now the problem for you is, there are at most 9 trains in the station, all the trains has an ID(numbered from 1 to n), the trains get into the railway in an order O1, your task is to determine whether the trains can get out in an order O2.
Input
The input contains several test cases. Each test case consists of an integer, the number of trains, and two strings, the order of the trains come in:O1, and the order of the trains leave:O2. The input is terminated by the end of file. More details in the Sample Input.
Output
The output contains a string "No." if you can't exchange O2 to O1, or you should output a line contains "Yes.", and then output your way in exchanging the order(you should output "in" for a train getting into the railway, and "out" for a train getting out of the railway). Print a line contains "FINISH" after each test case. More details in the Sample Output.
Sample Input
3 123 321 3 123 312
Sample Output
Yes. in in in out out out FINISH No. FINISH
For the first Sample Input, we let train 1 get in, then train 2 and train 3. So now train 3 is at the top of the railway, so train 3 can leave first, then train 2 and train 1. In the second Sample input, we should let train 3 leave first, so we have to let train 1 get in, then train 2 and train 3. Now we can let train 3 leave. But after that we can't let train 1 leave before train 2, because train 2 is at the top of the railway at the moment. So we output "No.".
Hint
Hint
直接上代码
#include<stdio.h>
#include<stack>
#include<queue>
using namespace std;
int main()
{
int n,i,t,status[200];char in[100],out[100];
while(scanf("%d%s%s",&n,in,out)!=EOF)
{
stack<char>si;
queue<char>qo;
for(t=i=0;i<n;i++)
{
status[t++]=0;//0代表 in
si.push(in[i]);
qo.push(out[i]);
while(si.top()==qo.front())
{
status[t++]=1;//1代表 out
si.pop();
qo.pop();
if(si.empty()&&qo.empty())//为空时跳出while
break;
}
}
if(si.empty()&&qo.empty())
{
puts("Yes.");
for(i=0;i<t;i++)
printf("%s\n",status[i]?"out":"in");
puts("FINISH");
}
else
puts("No.\nFINISH");
}
return 0;
}
看病要排队
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6272 Accepted Submission(s): 2596
Problem Description
看病要排队这个是地球人都知道的常识。
不过经过细心的0068的观察，他发现了医院里排队还是有讲究的。0068所去的医院有三个医生（汗，这么少）同时看病。而看病的人病情有轻重，所以不能根据简单的先来先服务的原则。所以医院对每种病情规定了10种不同的优先级。级别为10的优先权最高，级别为1的优先权最低。医生在看病时，则会在他的队伍里面选择一个优先权最高的人进行诊治。如果遇到两个优先权一样的病人的话，则选择最早来排队的病人。
现在就请你帮助医院模拟这个看病过程。
不过经过细心的0068的观察，他发现了医院里排队还是有讲究的。0068所去的医院有三个医生（汗，这么少）同时看病。而看病的人病情有轻重，所以不能根据简单的先来先服务的原则。所以医院对每种病情规定了10种不同的优先级。级别为10的优先权最高，级别为1的优先权最低。医生在看病时，则会在他的队伍里面选择一个优先权最高的人进行诊治。如果遇到两个优先权一样的病人的话，则选择最早来排队的病人。
现在就请你帮助医院模拟这个看病过程。
Input
输入数据包含多组测试，请处理到文件结束。
每组数据第一行有一个正整数N(0<N<2000)表示发生事件的数目。
接下来有N行分别表示发生的事件。
一共有两种事件：
1:"IN A B",表示有一个拥有优先级B的病人要求医生A诊治。(0<A<=3,0<B<=10)
2:"OUT A",表示医生A进行了一次诊治，诊治完毕后，病人出院。(0<A<=3)
每组数据第一行有一个正整数N(0<N<2000)表示发生事件的数目。
接下来有N行分别表示发生的事件。
一共有两种事件：
1:"IN A B",表示有一个拥有优先级B的病人要求医生A诊治。(0<A<=3,0<B<=10)
2:"OUT A",表示医生A进行了一次诊治，诊治完毕后，病人出院。(0<A<=3)
Output
对于每个"OUT A"事件，请在一行里面输出被诊治人的编号ID。如果该事件时无病人需要诊治，则输出"EMPTY"。
诊治人的编号ID的定义为：在一组测试中，"IN A B"事件发生第K次时，进来的病人ID即为K。从1开始编号。
诊治人的编号ID的定义为：在一组测试中，"IN A B"事件发生第K次时，进来的病人ID即为K。从1开始编号。
Sample Input
7 IN 1 1 IN 1 2 OUT 1 OUT 2 IN 2 1 OUT 2 OUT 1 2 IN 1 1 OUT 1
Sample Output
2 EMPTY 3 1 1
可以用数组解决
#include<stdio.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct pop
{
int rank,k;
}queue[3][2001];
bool cmp(struct pop x,struct pop y)
{
if(x.rank!=y.rank) return x.rank<y.rank;
return x.k>y.k;
}
int main()
{
int T,id,rank,k;char c,str[10];
while(scanf("%d",&T)!=EOF)
{
int u[3]={0,0,0};k=0;
while(T--)
{
scanf("%c%c",&c,&c);
if(c=='I')
{
scanf("N %d%d",&id,&rank);
queue[id-1][u[id-1]].rank=rank;
queue[id-1][u[id-1]].k=++k;
u[id-1]++;
}else
{
scanf("UT %d",&id);
sort(queue[id-1],queue[id-1]+u[id-1],cmp);
if(u[id-1])
{
printf("%d\n",queue[id-1][u[id-1]-1].k);
u[id-1]--;
}else puts("EMPTY");
}
}
}
return 0;
}
下面用优先队列
#include<stdio.h>
#include<queue>
using namespace std;
struct que
{
int id,rk;
bool friend operator < (que a,que b)
{
if (a.rk == b.rk)
return a.id > b.id;
return a.rk < b.rk;
}
/* 与以上代码效果差不多
bool operator < (const que &a)const{
if(rk!=a.rk)
return rk<a.rk;
else
return id>a.id;
}*/
}q;
int main()
{
int T,id,a,b,k;char c;
while(scanf("%d",&T)!=EOF)
{
k=1;
priority_queue<que>quee[3];
for(id=1;id<=T;id++)
{
scanf("%c%c",&c,&c);//第一个c吞掉一个换行
if(c=='I')
{
scanf("N %d%d",&a,&b);
q.id=k++;
q.rk=b;
quee[a-1].push(q);
}else
{
scanf("UT %d",&a);
if(quee[a-1].empty())
puts("EMPTY");
else
{
printf("%d\n",quee[a-1].top().id);
quee[a-1].pop();
}
}
}
}
return 0;
}
优先队列和sort的复杂度一样o(nlogn),就这个题优先队列比sort快一点点，可能是实现程序时算法复杂度低一些。