8.队列

发表于 分类于 ， 本文字数： 2.7k

队列

队列是一种“先入先出”的线性数据结构。可用一个数组和两个变量优化为循环队列或者STL实现。比如循环队列queue，双端队列deque，优先队列（二叉堆）priority_queue。

团体队列在这里插入图片描述

简单的队列套队列问题。题意其实很简单，就是开n+1个队列，一个队列存当前队伍中有几组，剩下n个队列，存的是自己组的人。每次入队的时候都是找自己的组员进队，并且会插队，所以出队的时候是当前组的组员全部出队以后，这个组没了，出下一组的人。

模拟优先队列

在这里插入图片描述

我们可以想一下，对于每一秒除了被切的哪一个所有的蚯蚓都增长q米，我们来维护3个队列，队列1表示最开始的蚯蚓，队列2表示每一次被切的蚯蚓被分开的较长的那一部分，队列3表示每一次被切的蚯蚓被分开的较短的那一部分。
我们先把原序列排序，因为不管怎么切，先被切的蚯蚓分成的两部分一定比后切的蚯蚓分成的两部分大(较大的部分和较大的部分比较，较小的部分和较小的部分比较)，所以我们可以省去每一秒增加每只蚯蚓的长度这个操作，转换成在查询砍那只蚯蚓时，把增加的长度算到蚯蚓的总长度上。
寻找每次砍哪一只蚯蚓就是在队列1、队列2、队列3的队头找一个算上增加的长度最大的蚯蚓，之后把他出队，切开的两部分分别进入队2、队3。

对于增量的计算我们可以按照蚯蚓在队列中的标号，因为队列1中的蚯蚓直到被切是一直处于一种增长状态，所以直接加上(当前时间-1) * q 就可以了，而对于队列2和队列3的蚯蚓，他的增长是从被切掉那一刻的下一秒开始的，所以他的增长量则是(当前时间-1-被切割的时间)*q。

单调队列与单调栈

单调栈和单调队列与普通的栈，队列不同点就是要维护他们元素的单调性（单增或单减），来实现相应的效果。要注意的是单调栈和单调队列即可以用数组模拟，也可以直接使用STL（更方便易于理解），但是如果用STL的话，单调栈/队列要在开始放入元素之前设置边界，单调递增就在边界（栈顶/队首）赋值为负值（<=0），单调递减就在边界赋值为INF(极大值)。因为如果栈/队列内无元素，那么s.top()是不合法的，这样就无法继续进行插入和删除操作来维护单调性。

如何维护单调：
每输入一个新元素就比较它是否符合单调要求，符合就push进去，不符合就把它前面的pop掉。

单调队列：
例如滑动窗口的要求要最多存几个元素，所以一旦越界就pop，一旦不单调就pop；
单调队列里新人是一定要进来的，老人可能都比新人弱而被全员踢出，但是踢干净以后立刻新人就push_back进来了，所以不会为空

###单调栈题

在这里插入图片描述

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<bits/stdc++.h>
using namespace std;
int n,temp,a,b,cnt;
stack<int>s;
int main()
{
    cin>>n;
    s.push(-1);//设边界
    cin>>a>>b;//本题中宽度没用
    s.push(b);
    for(int i=2;i<=n;i++)
    {
        cin>>a>>b;
        while(s.top()>=b)//一旦单调（递增）被破坏就把大与新人的都pop掉
        {
            temp=s.top();
            if(temp==b)cnt++;//若有相同的则可以省一张海报
            s.pop();
        }
        s.push(b);
    }
    cout<<n-cnt<<endl;//输出共需多少张海报即可
    return 0;
}


单调队列题

题目描述
一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。 

1
2
3
4
5
6
7
8
9
10
11
输入：
6 2
7 8 1 4 3 2
输出：
0
7
7
1
1
3

用STL中的deque实现的单调队列
注意这道题中新加入的成员是不能用的，必须等一个回合才能使用输出，所以应该模拟这个过程每次加入一个输出的是上一个加入时的最小值，所以只需要i<n即可，第n个数没用 

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
#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cmath>
#define debug cout<<"ok"<<endl
typedef long long ll;
const int maxn=20000010;
const int mod=1e9+7;
using namespace std;
struct node
{
    int index,vis;//index表示入队时间（序号），vis表示大小（权值）
}a[maxn];
deque<node>q;
int n,m,minn[maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].vis);
        a[i].index=i-1;
    }
    for(int i=1;i<n;i++)
    {
        if(q.empty())printf("0\n");
        while(!q.empty()&&q.back().vis>=a[i].vis)//维护队列两端的数据
            q.pop_back();//题目要求最小值，大于当前的值就直接pop掉
        q.push_back(a[i]);//每一个都push_back进去
        while(!q.empty()&&q.front().index+m<i)//超过长度就把前面超的pop掉
            q.pop_front();
        printf("%d\n",q.front().vis);
    }
    return 0;
}

https://blog.csdn.net/qq_44709990/article/details/120665261

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏