如何在优先级队列中运用结构体？- 洛谷平台P1878题目的解决方案
先讲一下怎样在优先队列中使用结构体。
众所周知，c++有一个好东西叫STL（不知道？以后我会讲的），STL中封装了大量的，现成的模板，比如今天我们要讲的优先队列。
定义方式：
priority_queue<typename> name;
其中 name 是指这个优先队列的名字，随便你怎么取，只要符合规定就可以了，typename 是指name的类型，如int，long long等。
优先队列默认是大的在前面，如何改变它的优先级呢（变成小的在前面）？
只要下面一行代码（举个例子，是int类型，名字为 q ）：
priority_queue<int,vector<int>,greater<int> > q;//注意了，这里要有两个空格，不然编译器会以为值右移
当然咯，你想要大的在前面，你也可以把 greater 改为 less 。
接下来讲一下如何在优先队列中支持结构体。
先假设结构体类型名为 node
先想一想，自己写排序cmp时是怎么写的。
int cmp(int a,int b){ return a>b; }//这是你写升序排序的代码
显然，这里的两个 int ，都要成为node，但计算机可不知道你要比较哪个！所以，你现在要重载> 或 < ，相当于你要让计算机明白你要比较node中的那个元素。
重载格式：
bool operator /*符号*/ (const typename &name1,const typename &name2){ /*在这里你可以写重载内容，和cmp大致一样
比如从大到小就写成return name1>name2 */ }
这些是你必须要知道的：
1.重定义任何一个符号和重载内容没有关系，比如
bool operator < (const int &a,const int &b){ return a>b; }
2.优先队列很奇怪，在具体实现是大于小于号都要反过来。
还有，我们写结构体优先队列时就不要写greater或less了（反正计算机也看不懂）
洛谷P1878题解
题目地址：https://www.luogu.com.cn/problem/P1878
分析：
这是一道非常明显，可以用优先队列的题（你也可以用堆）
现预处理一遍：相邻两个人性别不同时把他们的绝对值压入优先队列中。
找到符合条件的一对：绝对值最小且越靠左（越靠左！！我们写重载时会用得到）
先保存答案，再标记已经跳过，再看看他们两边有没有符合条件（一♂男♂一♂女，且没被标记跳过），如果有的话就压入队列。
具体实现看代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n; 4 char ch[505000]; 5 int a[505000]; 6 int vis[505000]; 7 struct node{ 8 int sum,x,y; 9 friend bool operator < (node a,node b){//结构体内定义要加friend 10 if(a.sum==b.sum)return a.x>b.x;//绝对值相等越靠左越优先 11 else return a.sum>b.sum;//绝对值从小到大 12 } 13 }; 14 priority_queue<node> q; 15 int k,ans_x[505000],ans_y[505000]; 16 int main(){ 17 scanf("%d",&n); 18 for(int i=1;i<=n;++i)cin>>ch[i]; 19 for(int i=1;i<=n;++i)scanf("%d",&a[i]); 20 for(int i=1;i<=n-1;++i){ 21 if(ch[i]!=ch[i+1])q.push(node{abs(a[i]-a[i+1]),i,i+1}); 22 } 23 while(!q.empty()){ 24 // cout<<q.top().sum<<endl; 25 int x=q.top().x; 26 int y=q.top().y; 27 q.pop(); 28 if(!vis[x]&&!vis[y]){//不能已经跳过 29 vis[x]=1; 30 vis[y]=1; 31 ++k; 32 ans_x[k]=x; 33 ans_y[k]=y; 34 while(x>=1&&vis[x])--x; 35 while(y<=n&&vis[y])++y;
//找到一对 36 if(x<1||y>n)continue;//不能越界 37 if(ch[x]!=ch[y])q.push(node{abs(a[x]-a[y]),x,y});//压进队列 38 } 39 } 40 cout<<k<<endl; 41 for(int i=1;i<=k;++i)cout<<ans_x[i]<<" "<<ans_y[i]<<endl; 42 return 0; 43 }
再说一下，优先队列复杂度为logn，所以总复杂度为nlogn
码字不易，点个赞再走吧QwQ
下一篇： C语言里的优先级队列详解：从入门到精通