Tang7O

优先队列简单讲解

Tang7O
ACM算法

发布于：2020年4月9日
次浏览
字数统计: 1.1k字   |   阅读时长: 5分

优先队列就是会自动排序的队列；

头文件`#include ；

声明格式为：priority_queue ans;//声明一个名为ans的整形的优先队列`

基本操作有： 

1
2
3
4
5
empty( ) //判断一个队列是否为空 
pop( ) //删除队顶元素 
top( ) //返回优先队列的队顶元素 
push( ) //加入一个元素 
size( ) //返回优先队列中的元素个数

默认的优先队列优先级高的排在前面，既优先级高的先出队列。

例如int型的优先队列数值大的排在前面、先出队列。

默认优先队列使用方法（优先级高先出队列）：

1
priority_queue<int> q1; //默认从大到小排序，整数中元素大的优先级高 
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
#include<cstdio>
#include<queue>
using namespace std;

int main()
{
    priority_queue<int> q1;//默认从大到小排序
    if(!q1.empty()) 
        q1.top();  //清空优先队列
    int n;
    scanf("%d",&n);
    int t;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&t);
        q1.push(t);
    }
    while(!q1.empty())
    {
        printf("%d ",q1.top());
        q1.pop();
    }
    return 0;
}


执行结果如下：

从大到小排序（优先级低的先出）；

1
2
priority_queue<int,vector<int>,greater<int> >q1;

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
#include<cstdio>
#include<queue>
using namespace std;

int main()
{
    priority_queue<int,vector<int>,greater<int> >q1;//从大到小排序，注意后面两个“>”不要写在一起，“>>”是右移运算符
    if(!q1.empty()) 
        q1.top();  //清空优先队列
    int n;
    scanf("%d",&n);
    int t;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&t);
        q1.push(t);
    }
    while(!q1.empty())
    {
        printf("%d ",q1.top());
        q1.pop();
    }
    return 0;
}


执行结果如下：

自定义排序：

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#include<queue>
using namespace std;
int tmp[100];
struct cmp1{
    bool operator()(int x,int y)
    {
        return x>y;//小的优先级高 ,从小到大排
    }
};
struct cmp2{
    bool operator()(const int x,const int y)
    {
        return tmp[x]>tmp[y];
    }
};
struct node{
    int x,y;
    friend bool operator<(node a,node b)
    {
        return a.x>b.x;//按x从小到大排
    }
};
priority_queue<int>q1;
priority_queue<int,vector<int>,cmp1>q2;
priority_queue<int,vector<int>,cmp2>q3;
priority_queue<node>q4;
int main()
{
    int i,n;
    node a;
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++)
        {
            scanf("%d %d",&a.y,&a.x);
            q4.push(a);
        }
        printf("\n");
        while(!q4.empty())
        {
            printf("%d %d\n",q4.top().y,q4.top().x);
            q4.pop();
        }
        printf("\n");

        int t;
        for(i=0;i<n;i++)
        {
            scanf("%d",&t);
            q2.push(t);
        }
        while(!q2.empty())
        {
            printf("%d\n",q2.top());
            q2.pop();
        }
        printf("\n");
    }
    return 0;
}


执行结果如下：

下面举个栗子： 题目链接

Stall Reservations

Description

Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A…B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows. Help FJ by determining: The minimum number of stalls required in the barn so that each cow can have her private milking period An assignment of cows to these stalls over time Many answers are correct for each test dataset; a program will grade your answer.

Input

Line 1: A single integer, N Lines 2…N+1: Line i+1 describes cow i’s milking interval with two space-separated integers.

Output

Line 1: The minimum number of stalls the barn must have. Lines 2…N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period.

Sample Input

5 1 10 2 4 3 6 5 8 4 7

Sample Output

4 1 2 3 2 4

题意：

思路

AC代码

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int Maxn=5e4+5;
typedef struct node
{
    int b,e,stall,id;
    friend bool operator< (node n1,node n2)
    {
        return n1.e > n2.e;
    }
} cow;
cow s[Maxn];

bool cmp1(cow x,cow y)
{
    return x.b < y.b;
}

bool cmp2(cow x,cow y)
{
    return x.id < y.id;
}

int main()
{
    int N;
    while(~scanf("%d",&N))
    {
        for(int i = 0; i < N; i++)
        {
            scanf("%d%d",&s[i].b,&s[i].e);
            s[i].id = i;
        }
        sort(s,s+N,cmp1);

        priority_queue<cow> que;
        s[0].stall = 1;
        que.push(s[0]);
        int cnt = 1;

        for(int i = 1; i < N; i++)
        {
            cow temp = que.top();
            if(s[i].b <= temp.e)
            {
                cnt++;
                s[i].stall = cnt;
                que.push(s[i]);
            }
            else
            {
                s[i].stall = temp.stall;
                que.pop();
                que.push(s[i]);
            }
        }
        sort(s,s+N,cmp2);
        printf("%d\n",cnt);
        for(int i = 0; i < N; i++)
            printf("%d\n",s[i].stall);
    }
    return 0;
}


本文作者： Tang7O

本文链接：https://tang7o.cn/2020/04/09/%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97%E7%AE%80%E5%8D%95%E8%AE%B2%E8%A7%A3/

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议。转载请注明出处！

更新于：2022年4月13日

算法

评论




博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

载入天数...载入时分秒... 本站使用 Volantis 作为主题

Copyright © 2017-2020 XXX

鲁ICP备-20012065号