优先队列
优先队列
第一次看hb写这个，感觉太高级了，定义一个结构都要一堆东西，甚是羡慕，感觉高级到爆炸。后来在入门经典上做题（抄代码）的时候，终于碰上了，这书之前倒是写过优先队列的定义。
所谓优先队列就是里面的元素有一定的优先级，比如数小的优先级高那么输出时先输出小的，等等。暑假的时候看了一点（点点点）数据结构，也就此知道实现用的是堆排序，速度比一般的插入排序东西快一点，也比较好维护，真的是很神奇。
优先队列类定义
template <class Type, class Container= vector <Type>,
class Compare= less <typename container ::value_type>>
成员函数
empty()
pop()
push()
size()
top()
三种优先级
priority_queue<int> q;//默认较大元素优先级高
priority_queue<int,vector<int>,greater<int>> q1;//较小元素优先级高
priority_queue<int,vector<int>,less<int>> q2;//较大元素优先级高
就这个神奇的东西为啥写做greater读作较小元素优先级高，莫名奇妙哦反着的（像不像数学分析里那个凹函数和凸函数好气哦），根据hb和我研究（瞎扯）得到的可能结论是在队列中数是先进先出的，所以当greater是大数时，就放在队尾，然后输出的时候不就在最后了嘛。
懒省事的小明
题目
标准的优先队列排序(说白了就是排序)
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
priority_queue<ll,vector<ll>,greater<ll>> q;
scanf("%d",&n);
ll a;
while(n--)
{
scanf("%lld",&a);
q.push(a);
}
ll ans=0;
while(q.size()>1)
{
ll x=q.top();
q.pop();
ll y=q.top();
q.pop();
ans+=x+y;//和再次放入优先队列，会自动siftdown或siftup
q.push(x+y);
}
printf("%lld\n",ans);
}
return 0;
}
倒水问题
题目
这题贼复杂(对于我对于我对于我)，我也不能说我会，书上说的很详细，看书吧
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=200+5;
int vis[maxn][maxn],ans[maxn],cap[3];//ans存放水为i时移动了多少水，要最小的
struct Node
{
int v[3],dist;
bool operator < (const Node& a)const
{
return dist>a.dist;
}
};
void update_ans(const Node& a)
{
for(int i=0;i<3;++i)
{
int d=a.v[i];
if(ans[d]<0||a.dist<ans[d])
ans[d]=a.dist;
}
}
void solve(int a,int b,int c,int d)//BFS
{
cap[0]=a,cap[1]=b,cap[2]=c;
memset(vis,0,sizeof(vis));
memset(ans,-1,sizeof(ans));
priority_queue<Node> q;
Node start;
start.dist=0;
start.v[0]=0,start.v[1]=0,start.v[2]=c;
q.push(start);
vis[0][0]=1;
while(!q.empty())
{
Node now=q.top();q.pop();
update_ans(now);
if(ans[d]>=0) //已经有一瓶水为d
break;
for(int i=0;i<3;++i)
for(int j=0;j<3;++j)
if(i!=j)
{
if(now.v[i]==0||now.v[j]==cap[j])//从i往j里倒
continue;
int amount=min(cap[j],now.v[i]+now.v[j])-now.v[j];
Node next;
memcpy(&next,&now,sizeof(now));
next.dist=now.dist+amount;
next.v[i]-=amount;
next.v[j]+=amount;
if(!vis[next.v[0]][next.v[1]])
{
vis[next.v[0]][next.v[1]]=1;
q.push(next);
}
}
}
while(d>=0)
{
if(ans[d]>=0)
{
printf("%d %d\n",ans[d],d);
return;
}
--d;
}
}
int main()
{
int T,a,b,c,d;
scanf("%d",&T);
while(T--)
{
scanf("%d %d %d %d",&a,&b,&c,&d);
solve(a,b,c,d);
}
return 0;
}
说这题的原因就是当定义了结构体时，优先队列里的比较该怎么写
方法：重载运算符’<’（必须是重载小于号）
所以当想要小的优先级高是只能反着来，返回时返回大于号
相关阅读
#include <bits/stdc++.h> using namespace std; const int maxn=10001; int main() { priority_queue<int>p; p.push(3)