admin管理员组

文章数量:1624338

STL priority_queue 具有“自动排序”的强大功能。其默认使用 operator< 的比较方式进行排序。
但是，对于自定义类型（如结构体、联合体、枚举等），则必须重载 operator< 比较方式。

对于官网链接为 http://acm.hdu.edu/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/showproblem.php?pid=1873 的题目“HDU 1873 - 看病要排队”，其一种实现即重载 operator< 比较方式。“HDU 1873 - 看病要排队”陈述详见 https://blog.csdn/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/hnjzsyjyj/article/details/124508284
https://blog.csdn/hnjzsyjyj/article/details/124514638
https://wwwblogs/Deribs4/p/5657746.html

本文标签： 时需元素结构priorityqueueoperator

版权声明：本文标题：priority_queue元素为结构体时需重载operator＜ 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dianzi/1728895851a1178395.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。