queue-概述：
队列中没有元素时，称为空队列。
|
bool empty() |
队列为空返回true，否则返回false |
|
void pop() |
删除队列的一个元素 |
|
void push( const TYPE &val ) |
将val元素加入队列 |
|
size_type size() |
返当前队列中的元素数目 |
|
TYPE &back() |
返回一个引用，指向队列的最后一个元素 |
|
TYPE &front() |
返回队列第一个元素的引用 |
|
bool empty() |
优先队列为空返回true，否则返回false |
|
void pop() |
删除优先队列中的第一个元素 |
|
void push( const TYPE &val ) |
添加一个元素到优先队列中，值为val |
|
size_type size() |
返当前队列中的元素数目 |
|
TYPE &top () |
返回一个引用，指向最高优先级的元素 |
#include<iostream>
#include<queue>
#include<set>
#include<vector>
using namespace std; void parse(vector<set<int> >&adj, unsigned int p=)//十分巧妙地递归读入。
{
unsigned int x;
cin>>x;
if(p)
{
adj[p].insert(x);
adj[x].insert(p);
}
while(true)
{
char ch;
cin>>ch;
if(ch==')') break;
parse(adj, x);
}
return;
} int main()
{
//freopen( "in.txt", "r", stdin );
//freopen( "out.txt", "w", stdout );
char ch;
while(cin>>ch)
{
vector<set<int> > adj(, set<int>());
parse(adj);
priority_queue<int, vector<int>, greater<int> >leafs;
int n = ;
for(unsigned int i = ; i<adj.size();i++)
if(adj[i].size())
{
n++;
if(adj[i].size()==)
leafs.push(i);
}
for(int k=; k<n; k++)
{
unsigned int x = leafs.top();
leafs.pop();
unsigned int p = *(adj[x].begin());
if(k>)
cout<<" ";
cout<<p;
adj[p].erase(x);
if(adj[p].size()==)
leafs.push(p);
}
cout<<endl;
}
return ;
}
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<iostream>
using namespace std; int main()
{
int n, k;
while(~scanf("%d%d", &n, &k))
{
priority_queue<int, vector<int>, greater<int> >que;
while(n--)
{
char op[];
scanf("%s", op);
if(op[]=='I')
{
int val;
scanf("%d", &val);
que.push(val);
while(que.size()>k) que.pop();
}
else printf("%d\n", que.top());
}
}
return ;
}
（提醒：不要直接交代码， 上面代码不能通过杭电的编译器）。
然后稍加改变， 编写自己的比较函数，而不是用自带的算子（greater）。 结果就过啦！ 也是十分的蛋疼，十分的无语！！!。
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<iostream>
using namespace std; struct Cmp{
bool operator()(const int&t1, const int&t2)
{
return t1>t2;
} }; int main()
{
int n, k;
while(~scanf("%d%d", &n, &k))
{
priority_queue<int, vector<int>,Cmp>que;
while(n--)
{
char op[];
scanf("%s", op);
if(op[]=='I')
{
int val;
scanf("%d", &val);
que.push(val);
while(que.size()>k) que.pop();
}
else printf("%d\n", que.top());
}
}
return ;
}
上面这个代码也不太好， 因为它有了太多的进队和出队， 每一次的进出都是需要维护优先队列的， 所以可以在入队满K个后， 在后来的插入时， 可以先比较一下， 然后决定是否插入。
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<iostream>
using namespace std; struct Cmp{
bool operator()(const int&t1, const int&t2)
{
return t1>t2;
} }; int main()
{
int n, k;
while(~scanf("%d%d", &n, &k))
{
priority_queue<int, vector<int>,Cmp>que;
int t = k;
char op[];
int val;
while(t--)
{
scanf("%s", &op);
scanf("%d", &val);
que.push(val);
}
n = n-k;
while(n--)
{
scanf("%s", &op);
if(op[]=='I')
{
scanf("%d", &val);
if(val>que.top())
que.push(val), que.pop();
}
else printf("%d\n", que.top()); }
}
return ;
}
一般优先队列的定义方法：
priority_queue< Type,vector<Type>,greater<Type> >(小顶堆)
priority_queue< Type,vector<Type>,less<Type> >(大顶堆)
如果是自定义的结构体类型
priority_queue<Node,vector<Node>,cmp>
需要自己自定义结构体类型：
struct cmp
{
bool operator()(const Node &t1,const Node &t2)
{
return t1.b<t2.b;//相当于less,大顶堆
}
};
3.又是一道可以用优先队列解的题。 优先队列的功能还真强大。
http://acm.hdu.edu.cn/showproblem.php?pid=4393
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std; struct Node{
int F;
int index;
friend bool operator<(Node a, Node b)
{
if(a.F!=b.F) return a.F<b.F;
else return a.index>b.index;
}
}; priority_queue<Node>q[];
int main()
{
int T;
int kase, n, S;
Node a;
scanf("%d", &T);
for(kase=; kase<=T; kase++)
{
scanf("%d", &n);
for(int i=; i<=n; i++)
{
scanf("%d%d", &a.F, &S);
a.index = i;
q[S].push(a);
}
printf("Case #%d:\n", kase);
for(int i=; i<n; i++)
{
int fast = -, id = ;
for(int j=; j<=; j++)
if(!q[j].empty())
{
Node tmp=q[j].top();
if(tmp.F+i*j>fast) fast=tmp.F+i*j, id=j;
else if(tmp.F+i*j==fast&&tmp.index<q[id].top().index) id = j;
}
printf("%d", q[id].top().index);
q[id].pop();
if(i<n-)printf(" ");
else printf("\n");
}
}
return ;
}