priority_queue 优先队列_自定义比较函数_four_means_综合

//
priority_queue< T,C<T>,cmpF >T : 数据类型 
C : 存储数据的容器
cmpF : 数据比较方式//
由于优先队列默认为大顶堆 重载 operator < 时 
bool operator < ( const T& a,const T& b )return true 说明 a < b
b 会被认为是大值 放在前面
a 会被认为是小值 放在后面
并不关心函数内部是如何定义的所以我们只需要 return ( a > b ) ; 
若成立, 函数认为b为大值, 被放在前面, 
其实b为小值, 这样就实现了小顶堆.所以 return true 表明 后者被放在前面
// 这与 sort_cmp 是完全相反的为了方便理解 我们可以在重载时 
将 判断语句/三元运算符 中 ab 位置对换一下
这样就很容易理解到底是怎么一个比较情况了此时 判断语句/三元运算符 内的情况 
就是我们希望得到的排序情况 // 忽略元素 只关注逻辑运算符本身第二种方法是一元谓词 本质也是一样
只不过将 AA 本身看成 a, 将 in 看成 b.

//
// 01 在结构体外重载 operator < 
struct AA
{int x,y;AA ( int a=0,int b=0 ):x(a),y(b) {}
};
bool operator < ( const AA& a,const AA& b )
{return ( b.x == a.x ) ? ( b.y < a.y ) : ( b.x < a.x ) ;
}
priority_queue<AA> q;
// const AA&
// const AA
// AA           
// AA&          (x)

//
// 02 在结构体内重载 operator < 一元谓词
struct AA
{int x,y;AA ( int a=0,int b=0 ):x(a),y(b) {}// 一元谓词 一定无 friend 一定有 constbool operator < ( const AA& in ) const  {return ( x == in.x ) ? ( y > in.y ) : ( x > in.x ) ;}
};
priority_queue<AA> q;
// const AA&
// const AA
// AA           
// AA&          (x)

//
// 03 在结构体内重载 operator < 二元谓词
struct AA
{int x,y;AA ( int a=0,int b=0 ):x(a),y(b) {}// 二元谓词 一定有 friend 一定无 constfriend bool operator < ( const AA& a,const AA& b ){return ( b.x == a.x ) ? ( b.y < a.y ) : ( b.x < a.x ) ;}
};
priority_queue<AA> q;
// const AA&
// const AA
// AA           
// AA&          (x)

//
// 04 自定义 比较类 仿函数
struct AA
{int x,y;AA ( int a=0,int b=0 ):x(a),y(b) {}
}; 
struct cmp
{                                               // 可以有 constbool operator () ( const AA& a,const AA& b ) const{return ( b.x == a.x ) ? ( b.y < a.y ) : ( b.x < a.x ) ;}
};
priority_queue< AA,vector<AA>,cmp > q;
// const AA&
// const AA
// AA           
// AA&          
// (均可)

// eg.01
#include<bits/stdc++.h>
using namespace std;//
// 01 在结构体外重载 operator < 
struct AA
{int x,y;AA ( int a=0,int b=0 ):x(a),y(b) {}
}in;
bool operator < ( const AA& a,const AA& b )
{return ( b.x == a.x ) ? ( b.y < a.y ) : ( b.x < a.x ) ;
}
priority_queue<AA> q;int main()
{int n;while( cin>>n ){while( n-- ){cin>>in.x>>in.y;q.push( in );}cout<<endl;while( q.size() ){cout<<q.top().x<<" "<<q.top().y<<endl;q.pop();}}return 0;
}
// 4
// 3 2
// 1 3
// 2 6
// 9 1// 1 3
// 2 6
// 3 2
// 9 1

// eg.02
#include<bits/stdc++.h>
using namespace std;//
// 02 在结构体内重载 operator < 一元谓词
struct AA
{int x,y;AA ( int a=0,int b=0 ):x(a),y(b) {}// 一元谓词 一定无 friend 一定有 constbool operator < ( const AA& in ) const  {return ( in.x == x ) ? ( in.y < y ) : ( in.x < x ) ;}
}in;
priority_queue<AA> q;int main()
{int n;while( cin>>n ){while( n-- ){cin>>in.x>>in.y;q.push( in );}cout<<endl;while( q.size() ){cout<<q.top().x<<" "<<q.top().y<<endl;q.pop();}}return 0;
}
// 4
// 3 2
// 1 3
// 2 6
// 9 1// 1 3
// 2 6
// 3 2
// 9 1

// eg.03
#include<bits/stdc++.h>
using namespace std;//
// 03 在结构体内重载 operator < 二元谓词
struct AA
{int x,y;AA ( int a=0,int b=0 ):x(a),y(b) {}// 二元谓词 一定有 friend 一定无 constfriend bool operator < ( const AA& a,const AA& b ){return ( b.x == a.x ) ? ( b.y < a.y ) : ( b.x < a.x ) ;}
}in;
priority_queue<AA> q;int main()
{int n;while( cin>>n ){while( n-- ){cin>>in.x>>in.y;q.push( in );}cout<<endl;while( q.size() ){cout<<q.top().x<<" "<<q.top().y<<endl;q.pop();}}return 0;
}
// 4
// 3 2
// 1 3
// 2 6
// 9 1// 1 3
// 2 6
// 3 2
// 9 1

// eg.04
#include<bits/stdc++.h>
using namespace std;//
// 04 自定义 比较类 仿函数
struct AA
{int x,y;AA ( int a=0,int b=0 ):x(a),y(b) {}
}in; 
struct cmp
{                                               // 可以有 constbool operator () ( const AA& a,const AA& b ) const{return ( b.x == a.x ) ? ( b.y < a.y ) : ( b.x < a.x ) ;}
};
priority_queue< AA,vector<AA>,cmp > q;int main()
{int n;while( cin>>n ){while( n-- ){cin>>in.x>>in.y;q.push( in );}cout<<endl;while( q.size() ){cout<<q.top().x<<" "<<q.top().y<<endl;q.pop();}}return 0;
}
// 4
// 3 2
// 1 3
// 2 6
// 9 1// 1 3
// 2 6
// 3 2
// 9 1