priority_queue本质是一个堆。
1、头文件是#include<queue>
2、关于priority_queue中元素的比较
模板申明带3个参数：priority_queue<Type, Container, Functional>，其中Type 为数据类型，Container为保存数据的容器，Functional 为元素比较方式。
Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector。
3、priority_queue<int> q; （这个int就是你要申请的类型， 此时默认的为大根堆，即依次弹出的数的顺序为从大到小）
如果要从小到大，则是这样：
priority_queue<int, vector<int>, greater<int> > q;
所以结构体就很容易想到了啊:
priority_queue<lpl> (lpl 为结构体的类型)
但是由于是结构体，那么它的比较大小的方式则也需要你来定义，所以你需要重载运算符。
题目描述
有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到N^2个和，求这N^2个和中最小的N个。
输入输出格式
输入格式：
第一行一个正整数N；
第二行N个整数Ai,满足Ai<=Ai+1且Ai<=10^9;
第三行N个整数Bi, 满足Bi<=Bi+1且Bi<=10^9.
【数据规模】
对于50%的数据中，满足1<=N<=1000；
对于100%的数据中，满足1<=N<=100000。
输出格式：
输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。
输入输出样例
3
2 6 6
1 4 8
3 6 7
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
struct lpl
{
int a;
int b;
int sum;
}lin;
bool operator < (lpl a, lpl b)
{
if(a.sum > b.sum) return true;
return false;
}
priority_queue<lpl> q;
int n;
int a[maxn], b[maxn];
void putit()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for(int i = 1; i <= n; ++i)
scanf("%d", &b[i]);
for(int i = 1; i <= n; ++i)
lin.a= 1, lin.b= i, lin.sum = a[1] + b[i], q.push(lin);
}
void workk()
{
for(int i = 1; i <= n; ++i)
{
lpl now = q.top();
q.pop();
printf("%d ", now.sum);
now.sum = a[now.a+ 1] + b[now.b];
now.a++;
q.push(now);
}
}
int main()
{
putit();
workk();
return 0;
}
原文链接：https://www.qiquanji.com/post/8112.html
本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。
微信扫码关注
更新实时通知