「优先队列」优先队列

优先队列

优先队列容器与队列一样，只能从队尾插入元素，从队首删除元素。但是它有一个特性，就是队列中优先级最大的元素总是位于队首，所以出队时，并非按照先进先出的原则进行，而是将当前队列中优先级最大的元素出队。这点类似于给队列里的元素进行了优先级由大到小的顺序排序。

元素的比较规则默认按元素值由优先级由大到小排序，可以重载“<”操作符来重新定义比较规则。

priority_queue<vector<int>, less<int> > pq1; 　　　 // 使用递增less<int>函数对象排序（大的放在首部）
priority_queue<deque<int>, greater<int> > pq2; 　　// 使用递减greater<int>函数对象排序

priority_queue<int> q;   　　　　　　　　　　　　  //通过操作，按照元素从大到小的顺序出队
priority_queue<int,vector<int>, greater<int> > q;  　　//通过操作，按照元素从小到大的顺序出队

例题：

upc第四次个人训练赛5502打地鼠

思路：

按时间排序，如果当遍历到某个点，时间超过了这个地鼠停留的时间，比较已在队列里的地鼠的最小价值和当前地鼠的价值，要大的那个。

代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iOStream>
#include<algorithm>
#include<queue>
using namespace std;
struct point
{
    int t;
    int v;
} p[100005];
bool cmp(point a,point b)
{
    if(a.t!=b.t)
    return a.t<b.t;
    return a.v>b.v;
}
priority_queue<int> q;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0; i<n; i++)
        {
            scanf("%d",&p[i].t);
        }
        for(int i=0; i<n; i++)
        {
            scanf("%d",&p[i].v);
        }
        sort(p,p+n,cmp);
        int ans=0;
        int tt=0;
        for(int i=0;i<n;i++)
        {
            if(tt<p[i].t)
            {
                tt++;
                q.push(-p[i].v);
                ans=ans+p[i].v;
            }
            else
            {
                int w=0-q.top();
                if(w>p[i].v)
                continue;
                ans=ans-w+p[i].v;
                q.pop();
                q.push(-p[i].v);
            }
        }
        printf("%d\n",ans);
    }
}

另一个题更能体现优先队列的好处：

upc专题训练排序c题

代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=1e5+5;
priority_queue<int,vector<int>, greater<int> > q;
int a[maxn];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            q.push(a[i]);
        }
        int num=0,num1=0,num2=0;
        for(int i=1; i<n; i++)
        {
            num1=q.top();
            q.pop();
            num2=num1+q.top();
            num+=num2;
            q.pop();
            q.push(num2);
        }
        printf("%d\n",num);
    }
}

之前错的地方是，我只排序了这一列数，然后从小到大相加，累计每个中间值，忽略了中间值可能比列中原有的剩余的数大的问题。

如果每次算完都排序的话，时间是O（n*n）;

所以用优先队列；

优先队列

优先队列

相关阅读

栏目导航

推荐阅读

热门阅读