侧边栏壁纸

【HTc++】优先队列

2024年06月12日 314阅读 0评论 1点赞

lxal87qr.png

基础函数

lxal8idl.png

#include "header.h"
#include <queue>
using namespace std;

int x;

int main()
{
    //定义一个int类型的 名为q的 优先队列
    priority_queue<int> q;
    //给优先队列q添加元素x
    q.push(x);
    //获取q中优先级最高元素
    q.top();
    //删除q中优先级最高元素
    q.pop();
    //返回q中元素个数
    q.size();
    /*
    判断q是否为空
    空->true  非->false
    */
    q.empty();

    return 0;
}

优先级判断

运算符重载

lxal93h2.png

2.1 重载运算符

重载运算符,对运算符重新定义、加载,赋予运算符不同的含义的函数语法。通常用于结构体 struct的运算、比较。
举例:

struct node{
    int key, val;
    bool operator<(const node& x) const {   
        //对<进行重载运算符,逻辑运算返回为bool类型,参数为x,另一个参数就是当前这个结构体
        return key < x.key;
        //对于node类型的变量<定义为 key较小的node < key较大的node
    }
};

2.2 构造函数

对结构体快速赋值的函数语法。
举例:

struct node{
    int key, val;
    node(int x, int y) {  //函数类型为结构体名
        key = x;
        val = y;
        //参数x赋值给key,y赋值给val
    }
};

构造函数之后可以对此类结构体进行赋值:

node n(1024, 2048);
node m = {First, Second};

2.3题目链接

lxalcxa1.png

样例

样例输入

3
2 6 6
1 4 8

样例输出

3 6 7

lxaleag0.png
lxalemz8.png

AC代码示例

/*AC代码1*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll n, a[N], b[N];
struct node{
    int x, y;
    ll val;
    bool operator<(const node& f) const {return val > f.val; }  //重载运算符,在优先队列中把val值小作为优先级
    node(int a, int b, ll c) {x = a; y = b; val = c; }  //构造函数
};
priority_queue<node> q;   //优先队列,node类型
map<pair<int, int>, bool> mp;  //map去重使用
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)  cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    sort(a + 1, a + n + 1);      //排序
    sort(b + 1, b + n + 1);
    q.push({1, 1, a[1] + b[1]});   //放入起始点{1, 1, a[1] + b[1]}
    while (n--) {
        int x = q.top().x, y = q.top().y;
        cout << q.top().val << " ";
        q.pop();
        if (!mp[make_pair(x + 1, y)]) {     //没用重复,放入{x + 1, y, a[x + 1] + b[y]}
            q.push({x + 1, y, a[x + 1] + b[y]});
            mp[make_pair(x + 1, y)] = true;   //标记
        }
        if (!mp[make_pair(x, y + 1)]) {    //没用重复,放入{x, y + 1, a[x] + b[y + 1]}
            q.push({x, y + 1, a[x] + b[y + 1]});
            mp[make_pair(x, y + 1)] = true;   //标记
        }
    }
    return 0;
}
/*AC代码2*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll n, a[N], b[N];
struct node{
    int x, y;
    ll val;
    bool operator<(const node& f) const {return val > f.val; }  //重载运算符,在优先队列中把val值小作为优先级
    node(int a, int b, ll c) {x = a; y = b; val = c; }  //构造函数
};
priority_queue<node> q;   //优先队列,node类型
map<pair<int, int>, bool> mp;  //map去重使用
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)  cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    sort(a + 1, a + n + 1);      //排序
    sort(b + 1, b + n + 1);
    q.push({1, 1, a[1] + b[1]});   //放入起始点{1, 1, a[1] + b[1]}
    while (n--) {
        int x = q.top().x, y = q.top().y;
        cout << q.top().val << " ";
        q.pop();
        if (!mp[make_pair(x + 1, y)]) {     //没用重复,放入{x + 1, y, a[x + 1] + b[y]}
            q.push({x + 1, y, a[x + 1] + b[y]});
            mp[make_pair(x + 1, y)] = true;   //标记
        }
        if (!mp[make_pair(x, y + 1)]) {    //没用重复,放入{x, y + 1, a[x] + b[y + 1]}
            q.push({x, y + 1, a[x] + b[y + 1]});
            mp[make_pair(x, y + 1)] = true;   //标记
        }
    }
    return 0;
}
1
打赏

—— 评论区 ——

昵称
邮箱
网址
取消
人生倒计时
最新评论
  • 人气很差!一条评论也没有!
舔狗日记