priority使用pair比较的坑点
所以用pair的priority_queue只能使用struct的重载比较,why?!
重载运算符的操作不能用于pair类型数据的排序,只能作用于结构体或类对象。—> 所以不能使用node型的priority_queue的函数重载操作符的方法
node可以函数操作符重载
![node可以函数操作符重载 https://cdn.jsdelivr.net/gh/wolfdan666/BlogPic/%E7%AE%97%E6%B3%95/%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97/node%E5%8F%AF%E4%BB%A5%E5%87%BD%E6%95%B0%E9%87%8D%E8%BD%BD.png](/svg/loading.min.svg)
pair不支持重载运算符
![pair不支持重载运算符 https://cdn.jsdelivr.net/gh/wolfdan666/BlogPic/%E7%AE%97%E6%B3%95/%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97/pair%E4%B8%8D%E6%94%AF%E6%8C%81%E9%87%8D%E8%BD%BD%E8%BF%90%E7%AE%97%E7%AC%A6.png](/svg/loading.min.svg)
priority_queue定义不支持"嵌入式"函数重载的方法,即 priority_queue<P, vector<P>, cop >
这样会报错 sort(a,a+n,cop)
可以
比较区只有strut定义
![比较区只有strut定义 https://cdn.jsdelivr.net/gh/wolfdan666/BlogPic/%E7%AE%97%E6%B3%95/%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97/struct%E6%AF%94%E8%BE%83.png](/svg/loading.min.svg)
嵌入式函数重载报错
![嵌入式函数重载报错 https://cdn.jsdelivr.net/gh/wolfdan666/BlogPic/%E7%AE%97%E6%B3%95/%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97/%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%87%BD%E6%95%B0%E9%87%8D%E8%BD%BD%E6%8A%A5%E9%94%99.png](/svg/loading.min.svg)
综上:不能函数重载了,那么就只能struct的自定义重载了咯
![strut自定义比较函数 https://cdn.jsdelivr.net/gh/wolfdan666/BlogPic/%E7%AE%97%E6%B3%95/%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97/strut%E8%87%AA%E5%AE%9A%E4%B9%89%E6%AF%94%E8%BE%83%E5%87%BD%E6%95%B0.png](/svg/loading.min.svg)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <iostream> // cout
#include <queue> // priority_queue
using namespace std;
struct node {
int x, y;
};
bool operator<(const node& a, const node& b)
{
return a.y > b.y; //less默认大顶堆,改为小顶堆
}
bool cop(const P& a, const P& b) { return a.second > b.second; }
typedef pair<int, int> P;
struct cmp1 {
// 就是说在cmp里面,当两个P使用 ()的时候,他们使用的下面的函数,也就是创建了一个自定义的函数
/* 使用时 大概是这样的 cmp1 A, A(a,b) 就类似 非strut的自定义函数了
bool cmp(P a,P b){ return a.second<b.second;}
*/
bool operator()(P a, P b){ // 重载() 的函数 叫 仿函数-->紫书找到的
return a.second > b.second; //小顶堆
}
};
int main(){
cout << "Popping out elements...";
// priority_queue<node, vector<node>, less<node>> test;
priority_queue<P, vector<P>,cmp1> test;
test.push({ 3, 2 });
test.push({ 1, 6 });
test.push({ 2, 8 });
test.push({ 5, 10 });
while (!test.empty()) {
cout << ' ' << test.top().second;
// cout << ' ' << test.top().y;
test.pop();
}
cout << endl;
return 0;
}
|
2019年7月9日23:27:19 更第一波
题集
注: 为了统一性,所以一般链接地址都是用的Virtual Judge的链接地址,只有VJ上没有的才用其他链接
2019年7月13日第一更
poj3190
牛客重现2019矿大省赛G题
附录
priority_queue各种实现方式的时间复杂度对比
![priority_queue各种实现方式的时间复杂度对比 https://cdn.jsdelivr.net/gh/wolfdan666/BlogPic/%E7%AE%97%E6%B3%95/%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97/%E5%90%84%E7%A7%8D%E5%AE%9E%E7%8E%B0%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6.png](/svg/loading.min.svg)