发布作者: ZHWEI
百度收录: 正在检测是否收录...
作品采用: 《 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 》许可协议授权
#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;
}
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题目链接
样例
样例输入
3 2 6 6 1 4 8
样例输出
3 6 7
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; }
—— 评论区 ——