博客

STL priority_queue 具有“


自动排序


”的强大功能。其默认使用


operator<


的比较方式进行排序。

但是，对于


自定义类型


（如结构体、联合体、枚举等），则必须


重载 operator<


比较方式。

对于官网链接为 http://acm.hdu.edu.cn/showproblem.php?pid=1873 的题目“


HDU 1873 – 看病要排队


”，重载 operator< 的示例代码如下所示：

bool operator<(Node a,Node b){
	if(a.pr!=b.pr)
		return a.pr<b.pr;
	else
		return a.index>b.index;
}

注意：

不少人表示难以理解上面重载 operator< 的示例代码。

为了解决此问题，现在给出一种虽不严谨但较易理解的表述，

即“



若a.pr<b.pr，则Node a<Node b




，即Node a的优先级小于Node b的优先级；




若a.index>b.index，则Node a<Node b




，即Node a的优先级小于Node b的优先级

”。这是因为，题目“


HDU 1873 – 看病要排队


”规定“医生在看病时，则会在他的队伍里面选择一个优先权最高的人进行诊治。如果遇到两个优先权一样的病人的话，则选择最早来排队的病人”。而


上述代码中，pr表示病人的优先级，index表示病人排队的先后顺序。显然，若病人a的优先级小于病人b的优先级，即a.pr<b.pr，则病人b先看病，即Node a<Node b。同理，若病人a来的比病人b晚，即a.index>b.index，则病人b先看病，即Node a<Node b。

例如，对于官网链接为 http://acm.hdu.edu.cn/showproblem.php?pid=1873 的题目“


HDU 1873 – 看病要排队


”，其一种实现即


重载 operator<


比较方式。“HDU 1873 – 看病要排队”陈述详见 https://blog.csdn.net/hnjzsyjyj/article/details/124508284 链接。代码如下：

#include <bits/stdc++.h>
using namespace std;
 
struct Node{
	int pr,index;
};
 
bool operator<(Node a,Node b){
	if(a.pr!=b.pr)
		return a.pr<b.pr;
	else
		return a.index>b.index;
}
 
int main(){
	int n;
	while(cin>>n){
		priority_queue<Node> q[3];
		int cnt=0;
		while(n--){
			char s[5];
			cin>>s;
			if(s[0]=='I'){
				int id,pr;
				Node node;
				cnt++;
				cin>>id>>pr;
				node.pr=pr;
				node.index=cnt;
				q[id-1].push(node);
			} else {
				int id;
				cin>>id;
				if(q[id-1].empty())
					cout<<"EMPTY"<<endl;
				else
					cout<<q[id-1].top().index<<endl,q[id-1].pop();
			}
		}
	}
	return 0;
}
 
/*
in:
7
IN 1 1
IN 1 2
OUT 1
OUT 2
IN 2 1
OUT 2
OUT 1
2
IN 1 1
OUT 1
out:
2
EMPTY
3
1
1
*/

【参考文献】



https://blog.csdn.net/hnjzsyjyj/article/details/124508284

https://blog.csdn.net/hnjzsyjyj/article/details/124514638

https://www.cnblogs.com/Deribs4/p/5657746.html