STL---priority_queue zoj_2212,zoj_2724,zoj_3230

          priority_queue顾名思意是优先队列的意思，在STL内部的实现形式是堆。使用priority_queue的关键就是重载比较函数，去实现不同要求的堆。另外，值得注意的是，二叉堆实现的优先队列是不稳定的，这点要特别注意

         在重载优先队列比较函数的时候注意是重载一个类，在类中重写一个（）操作符。

class problem
{
public:
	int a,b;
};//定义prblem类型
struct cmp
{
	bool operator()(const problem x,const problem y)
	{
		return x.b<y.b;//极大堆
	}
};//重载比较函数
priority_queue<problem,vector<problem>,cmp >q;//声明优先队列

 如下：

 zoj_2212

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
using namespace std;
class reg
{
	public:
		int num;
		int per;
		int n;
		reg(int num,int per,int n)
		{
			this->num=num;
			this->per=per;
			this->n=n;
		}
};
struct cmp
{
	bool operator()(const reg a,const reg b)
 	{
  		//return a>b;//最小堆
  		//return a<b;//最大堆
		if(a.n==b.n)
			return a.num>b.num;
		return a.n>b.n;
 	}
};
int k;
string s;
int main()
{
	freopen("e:\\zoj\\zoj_2212.txt","r",stdin);
	priority_queue< reg, vector < reg > , cmp >q;
	while(cin>>s&&s!="#")
	{
		int num,per;
		cin>>num>>per;
		//for(int i=1;i<=5;i++)
		//q.push(reg(num,per,per*i));
		q.push(reg(num,per,per));
	}
	cin>>k;
	for(int i=0;i<k;i++)
	{
		reg g=q.top();
		q.pop();
		reg a(g.num,g.per,g.n+g.per);
		q.push(a);
		cout<<g.num<<endl;	
	}
	return 0;
}

 

zoj_2724

#include<iostream>
#include<queue>
#include<cstdio>
#include<string>
#include<string.h>
using namespace std;
class message
{
public:
	char name[20];
	int parameter;
	int priority;
};
struct cmp
{
	bool operator()(const message a,const message b)
 	{
  		//return a>b;//最小堆
  		//return a<b;//最大堆
		return a.priority>b.priority;
 	}
		
};
int main()
{
	//string s;
	char ch[3];
	priority_queue< message, vector < message > , cmp >q;
	freopen("e:\\zoj\\zoj_2724.txt","r",stdin);
	while(scanf("%s",ch)!=EOF)
	{
		if(!strcmp(ch,"PUT"))
		{
			//string s1;
			char name[20];
			int para,p;
			//cin>>s1>>para>>p;
			message m;
			scanf("%s %d %d",&m.name,&m.parameter,&m.priority);
			q.push(m);
		}
		if(!strcmp(ch,"GET"))
		{
			if(!q.empty())
			{
				message m=q.top();
				q.pop();
				//cout<<m.name<<" "<<m.parameter<<endl;
				printf("%s %d\n",m.name,m.parameter);
			}
			else
				//cout<<"EMPTY QUEUE!"<<endl;
				printf("EMPTY QUEUE!\n");
		}

	}
		
}

 zoj_3230

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
class problem
{
public:
	int a,b;
};
struct cmp
{
	bool operator()(const problem x,const problem y)
	{
		return x.b<y.b;//升序
	}
};
bool cmp2(const problem x,const problem y)
{
	return x.a<y.a;//极大堆
}
int m,n,p,a,b;
problem plist[100005];
int main()
{
	freopen("e:\\zoj\\zoj_3230.txt","r",stdin);
	priority_queue<problem,vector<problem>,cmp >q;
	while(cin>>n>>m>>p)
	{
		while(!q.empty())
			q.pop();
		for(int i=0;i<n;++i)
		{
			cin>>a>>b;
			problem pr;
			pr.a=a;
			pr.b=b;
			plist[i]=pr;	
		}
		sort(plist,plist+n,cmp2);
		for(int i=0;i<n;i++)
		{
			if(m==0)
				break;
			if(plist[i].a<=p)
			q.push(plist[i]);
			else
			{
				if(!q.empty())
				{
				problem pr=q.top();
				p+=pr.b;
				--m;
				--i;
				q.pop();
				}
				else
				break;
			}
		}
		while(m--)
		{
			if(!q.empty())
			{
				problem pr=q.top();
				p+=pr.b;
				q.pop();	
			}
			else
				break;
		}
		cout<<p<<endl;
	}	
}