STL中priority_queue总结

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,我们将及时处理。

微信扫码关注

更新实时通知