ACM.优先队列

Bertha 。 2023-07-05 10:14 17阅读 0赞

优先队列种比较函数的写法。  
可以通过重载“<”操作符来重新定义比较规则，优先队列中元素的比较规则默认是按元素的值从大到小排序；  
切记：从小到大排序采用“>”号；如果要从大到小排序，则采用“<”号。  
可写作：

bool operator < (const node &s1,const node &s2)
    {
        
    return a.sum>b.sum;//表示的是从小到大排序
    }

！！比较关系是与cmp函数相反的。

## 优先队列例题 ##

一.买饭-优先队列  
Problem:A  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
林大食堂非常拥挤，得排队买饭，陈老师也是一样的！  
有n个人在一个卖饭窗口前排队买饭，假如每个人买饭的时间为t,请编程找出一种这n个人排队的顺序，使得这n个人的平均等待时间最小。  
Input  
第一行一个n(1<=n<=1000),  
第2行分别表示每人的接水时间t1,t2,t3,…tn，1<=t\[i\]<=10000；  
Output  
第1行为排队顺序；  
第2行为平均等待时间（结果保留2位小数）；  
Sample Input  
10  
56 12 1 99 1000 234 33 55 99 812  
Sample Output  
3 2 7 8 1 4 9 6 10 5  
291.90

当轮到某一个人买饭时，这段时间不计算在他的等待时间中。  
让买饭时间少的人先买，这样平均时间最少。

#include <bits/stdc++.h>
    using namespace std;
    int n,x;
    struct node
    {
        
        int x,num;
    };
    bool operator < (const node &s1,const node &s2)//结构体自定义比较，重载运算符
    {
        
        if(s1.x!=s2.x)return s1.x>s2.x;
        return s1.num>s2.num;
    }
    priority_queue<node,vector<node> >q;
    int main()
    {
        
         ios::sync_with_stdio(false);
        cin>>n;
        for(int i=1;i<=n;i++)
        {
        
            cin>>x;
            q.push({
        x,i});
        }
        double sum=0,now=0;
        while(!q.empty())
        {
        
            node tp=q.top();
            q.pop();
            sum+=now;
            now+=1.0*tp.x;
            q.empty()?printf("%d\n",tp.num):printf("%d ",tp.num);
        }
        printf("%.2lf\n",sum/(n*1.0));
        return 0;
    }

二.合并果子-优先队列  
Problem:B  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。  
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。  
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1 ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。  
例如有 3 种果子，数目依次为 1 ， 2 ， 9 。可以先将 1 、 2 堆合并，新堆数目为 3 ，耗费体力为 3 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为 12 。所以多多总共耗费体力 =3+12=15 。可以证明 15 为最小的体力耗费值。  
Input  
共两行。  
第一行是一个整数 n(1≤n≤10000) ，表示果子的种类数。  
第二行包含 n 个整数，用空格分隔，第 i 个整数 ai(1≤ai ≤20000) 是第 i 种果子的数目。  
Output  
一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 2^31。  
Sample Input  
3  
1 2 9  
Sample Output  
15

优先队列的模板题，水。

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        priority_queue<int,vector<int>,greater<int> >q1;
        int n;
        long long HP=0;
        scanf("%d",&n);
        int a[n+1];
        for(int i=1;i<=n;i++)
        {
        
            scanf("%d",&a[i]);
            q1.push(a[i]);
        }
        while(q1.size()>1)
        {
        
            int tmp1=q1.top();
            q1.pop();
            int tmp2=q1.top();
            q1.pop();
            int tmp3=tmp1+tmp2;
            HP+=tmp3;
            q1.push(tmp3);
        }
        printf("%lld\n",HP);
        return 0;
    }

三.序列合并-优先队列  
Problem:C  
Time Limit:2000ms  
Memory Limit:65535K  
Description  
给出两个长度为 n 的有序表 A 和 B，在 A 和 B 中各任取一个元素，可以得到 n^ 2 个和，求这些和中最小的 n 个。  
Input  
第 1 行包含 1 个整数 n（1≤n≤400000）。  
第 2 行与第 3 行分别有 n 个整数，各代表有序表 A 和 B。一行中的每两个整数之间用一个空格隔开，大小在长整型范围内，数据保证有序表单调递增。  
建议用scanf()读入，否则会TLE!  
Output  
输出共 n 行，每行一个整数，第 i 行为第 i 小的和。  
数据保证在 long long 范围内。  
Sample Input  
3  
2 6 6  
1 4 8  
Sample Output  
3  
6  
7  
首先，把A和B两个序列分别从小到大排序，变成两个有序队列。这样，从A和B中各任取一个数相加得到N2个和，可以把这些和看成形成了n个有序表/队列：  
A\[1\]+B\[1\] <= A\[1\]+B\[2\] <= … <= A\[1\]+B\[N\]  
A\[2\]+B\[1\] <= A\[2\]+B\[2\] <= … <= A\[2\]+B\[N\]  
……  
A\[N\]+B\[1\] <= A\[N\]+B\[2\] <= … <= A\[N\]+B\[N\]  
接下来，就相当于要将这N个有序队列进行合并排序：  
首先，将这N个队列中的第一个元素放入一个优先队列中；  
然后，每次取出堆中的最小值。若这个最小值来自于第k个队列，那么，就将第k个队列的下一个元素放入堆中。  
时间复杂度：O(NlogN)。不清楚为什么可以这么算，记，就硬记。

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=4e5+10;
    int n,a[N],b[N];
    struct node
    {
        
        int x,y;
        ll sum;
    };
    bool operator < (const node &s1,const node &s2)
    {
        return s1.sum>s2.sum;}
    priority_queue<node,vector<node> >q;
    int main()
    {
        
        ios::sync_with_stdio(false);
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            cin>>b[i];
        for(int i=1;i<=n;i++)
            q.push({
        i,1,a[i]+b[1]});
        for(int i=1;i<=n;i++)
        {
        
            node tmp=q.top();q.pop();
            i==n?printf("%lld\n",tmp.sum):printf("%lld ",tmp.sum);
            int x=tmp.x,y=tmp.y;
            q.push({
        x,y+1,a[x]+b[y+1]});//把上一个输出最小的同一行的下一个入队
        }
        return 0;
    }

四.合成陨石-优先队列  
Problem:D  
Time Limit:1000ms  
Memory Limit:65536K  
Description  
fz大学化学系的学生们最近发现了一种奇怪的陨石，这些陨石通过化学反应合成，会放出惊人的破坏力量。为了储存方便，化学系的学生们决定把这些陨石碎块合成一个大的陨石块。每一次合并，可以把两个陨石合成一个，放出的破坏能量是两个陨石的质量之和，而新产生的陨石质量是这两个陨石的质量之和。  
为了将这次试验的破坏效果减少到最低，他们想请你帮忙，计算一下可以达到的最小破坏能量值。  
例如有3个陨石碎片，质量依次为1，2，9。可以先将1、2合并，新陨石为3，放出的破坏能量为3。接着，将新陨石与原先的3合并，又得到新的陨石，质量为12，放出的破坏能量为12。所以总共放出的破坏能量=3+12=15。可以证明15为最小的破坏能量值。  
Input  
多组数据输入.  
每组输入两行，第一行是一个整数n(1<＝n<=10000)，表示陨石的个数。第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i个陨石的质量。  
Output  
每组输出一个整数，也就是最小的破坏能量值。输入数据保证这个值小于2^31。  
Sample Input  
3  
1 2 9  
Sample Output  
15  
模板题，水。

#include <bits/stdc++.h>
    using namespace std;
    int n;
    int main()
    {
        
        priority_queue<int,vector<int>,greater<int> >q;
        while(scanf("%d",&n)!=EOF)
        {
        
         int a[n+1];
         for(int i=1;i<=n;i++)
         {
        
             scanf("%d",&a[i]);
             q.push(a[i]);
         }
         long long sum=0;
         while(q.size()>1)
         {
        
             int tmp1=q.top();
             q.pop();
             int tmp2=q.top();
             q.pop();
             int tmp3=tmp1+tmp2;
             sum+=tmp3;
             q.push(tmp3);
         }
         q.pop();
         printf("%lld\n",sum);
         sum=0;
        }
        return 0;
    }

五.堆-优先队列  
Problem:E  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
如题，初始小根堆为空，我们需要支持以下3种操作：  
操作1： 1 x 表示将x插入到堆中  
操作2： 2 输出该小根堆内的最小数  
操作3： 3 删除该小根堆内的最小数  
Input  
第一行包含一个整数N，表示操作的个数（1<=N<=1000000）  
接下来N行，每行包含1个或2个正整数，表示三种操作，格式如下：  
操作1： 1 x  
操作2： 2  
操作3： 3  
Output  
包含若干行正整数，每行依次对应一个操作2的结果  
Sample Input  
5  
1 2  
1 5  
2  
3  
2  
Sample Output  
2  
5

理解优先队列的本质，是一个树形的堆结构，代码不难。

#include <bits/stdc++.h>
    using namespace std;
    priority_queue<int,vector<int>,greater<int> >q;
    int main()
    {
        
        int n,a,b;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
        
            scanf("%d",&a);
            if(a==1)scanf("%d",&b),q.push(b);
            else if(a==2)printf("%d\n",q.top());
            else q.pop();
        }
        return 0;
    }

六.瑞瑞的木板-优先队列  
Problem:F  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
瑞瑞想要亲自修复在他的一个小牧场周围的围栏。他测量栅栏并发现他需要N（1≤N≤20,000）根木板，每根的长度为整数Li（1≤Li≤50,000）。于是，他神奇地买了一根足够长的木板，长度为所需的N根木板的长度的总和，他决定将这根木板切成所需的N根木板。（瑞瑞在切割木板时不会产生木屑，不需考虑切割时损耗的长度)瑞瑞切割木板时使用的是一种特殊的方式，这种方式在将一根长度为x的模板切为两根时，需要消耗x个单位的能量。瑞瑞拥有无尽的能量，但现在提倡节约能量，所以作为榜样，他决定尽可能节约能量。显然，总共需要切割N-1次，问题是，每次应该怎么切呢？请编程计算最少需要消耗的能量总和。  
Input  
第一行: 整数N，表示所需木板的数量  
第2到N+1行: 每行为一个整数，表示一块木板的长度  
Output  
一个整数，表示最少需要消耗的能量总和  
Sample Input  
3  
8  
5  
8  
Sample Output  
34

想想后，其实就是上一道合并果子的题的逆过程，写法基本一致。

#include <bits/stdc++.h>
    using namespace std;
    priority_queue<int,vector<int>,greater<int> >q;
    int main()
    {
        
        int n;
        scanf("%d",&n);
        int a[n+1];
        long long sum=0;
        for(int i=1;i<=n;i++)
        {
        
            scanf("%d",&a[i]);
            q.push(a[i]);
        }
        while(q.size()>1)
        {
        
            int tmp1=q.top();
            q.pop();
            int tmp2=q.top();
            q.pop();
            q.push(tmp1+tmp2);
            sum+=tmp1;
            sum+=tmp2;
        }
        printf("%lld\n",sum);
        return 0;
    }

七.桐桐的新闻系统-优先队列  
Problem:G  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
桐桐为期末的计算机作业设计了一套新闻系统，他把这套系统称为Argus;  
使用这套系统的用户可以向这套系统注册，然后这套系统就会以用户要求发送新闻的时间间隔向用户发送一次新闻。向Argus注册的指令具有以下格式：  
Register Q\_num Period  
Q\_num(0 < Q\_num<=3000)是用户的ID，Period(0 < Period <= 3000)是间隔。注册后Period秒，结果会第一次到达。所有的用户都有不同的Q\_num。桐桐测试了一段时间后，想知道系统前K次给谁发送新闻了。如果同一时间发送多个新闻，以Q\_num的升序排列。  
Input  
第一部分是注册指令，每条一行。指令数不超过1000，所有人指令同时执行完。此部分以“＃”结束。  
第二部分仅一行一个正整K，K<=10000  
Output  
输出前K个新闻发送到的用户的Q\_num,每行一个。  
Sample Input  
Register 2004 200  
Register 2005 300

#  #

5  
Sample Output  
2004  
2005  
2004  
2004  
2005

理解题目的意思，为了输出前k个用户的id，需要建立一个时间轴，以便处理先后的过程。

#include <bits/stdc++.h>
    using namespace std;
    struct node
    {
        
        int id;
        int cost;//每个人花费的时间
        int time;//当前经过总时间，时间不断向前走
    };
    bool operator < (const node &s1,const node &s2)
    {
        
        if(s1.time!=s2.time)return s1.time>s2.time;//根据当前的时间比较先后顺序
        return s1.id>s2.id;
    }
    priority_queue<node,vector<node> >q;
    int main()
    {
        
         ios::sync_with_stdio(false);
         char s[11];
         int id,cost,k;
         while(cin>>s&&s[0]!='#')
         {
        
             cin>>id>>cost;
             q.push({
        id,cost,cost});//当轮到某一个请求时，此时时间一定是加上了cost，所以初始的time值为cost
         }
         cin>>k;
         while(k--){
        //只记录k次
            node tp=q.top();
            q.pop();
            printf("%d\n",tp.id);
            q.push({
        tp.id,tp.cost,tp.time+tp.cost});//下一个入队的总时间要加上上一个请求经过的时间。
         }
        return 0;
    }