priority_queue优先队列容器。(爱上原创和改造) Priority_queue优先队列容器与队列一样,只能在队尾插入元素,从队首删除元素。但是它还有一个特性,就是队列中最大的元素总是位于队首。所以出队时,并非按照先进先出的原则进行,而是将队列中的最大的元素,出队。这点类似于给队列里的元素进行了,由大到小的顺序排序。元素的比较规则默认为按元素的值由大到小排序,当然我们可以重载”<”操作符来重新定义比较规则,当然我们可以重载”()”操作符的方式来定义优先级。使用priority_queue的头文件为#include
<queue>
http://acm.nyist.net/JudgeOnline/problem.php?pid=55
官方解答是是利用multiset容器。相关内容我会在另一篇博文中更新。。
下面说明两种方式来确定队列中元素的排列顺序。。。注意下面的代码不是用来AC题目的。。但是你只要理解了。。AC不是问题。。
#include<iostream> #include<cstdio> #include<cstdlib> #include<vector> #include<algorithm> #include<queue> #include<set> #include<map> #include<string> #include<cstring> using namespace std; const int max=11000; struct Info{ stringname; doublescore; booloperator < (const Info & a) const{ //按score小到大排序,注意比较两个元素的位置习惯,这样我们就可以直接看出是从小到大还是从大到小。 returna.score < score; } } struct myCp{ booloperator ()(const &a,const int &b){ //按元素的从小到大顺序,注意代码中两个元素的位置习惯,当然这是个人爱好。 //很明显和上面的重载"<"操作符一样。我都把后面的元素写在前面,然后进行与前面的比较, //这样"<"就是从小到大,">"就是从大到小。 returnb<a; } } int main() { //方法一:重载"<"运算符来定义优先级,适合其中的元素为结构体类型 priority_queue< Info> pq; Infoinfo; info.name="jack";info.score=100.0; pq.push(info); info.name="tom";info.score=200.45; pq.push(info); info.name="peti";info.score=50.75; pq.push(info); //以上给priority_queue队列赋值三个元素 //以下priority_queue出队。 while(pq.empty()!=true){ cout<<pq.top().name<<":"<<pq.top().score<<endl; pq.pop(); } //方法二:重载“()”运算符来定义优先级。元素为基本类类型比较好用。 priority_queue<int,vector<int>,myCp> pq2;//注意其中的三个参数。 pq2.push(2);pq2.push(3);pq2.push(5); while(!pq2.empty()){ cout<<pq2.top()<<""; pq2.pop(); } cout<<endl; return 0; }