目录
- 单调队列
队列是一种 “先进先出” 的线性数据结构。
【例题】小组队列
有 n 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
40
41
42
43
44
45
46
47
48
49
50#include <bits/stdc++.h> using namespace std; const int N = 1003; int Hash[N * N]; int main() { int t, T = 1; while(scanf("%d", &t) && t) { memset(Hash, 0, sizeof Hash); queue<int> Q; queue<int> q[N]; for(int i = 1, n; i <= t; ++i) { scanf("%d", &n); for(int j = 0, x; j < n; ++j) { scanf("%d", &x); Hash[x] = i; } } string op; int x; printf("Scenario #%dn", T++); while(cin >> op && op != "STOP") { if(op == "ENQUEUE") { cin >> x; int p = Hash[x]; if(q[p].empty()) Q.push(p); q[p].push(x); } else { int p = Q.front(); x = q[p].front(); cout << x << endl; q[p].pop(); if(q[p].empty()) Q.pop(); } } puts(""); } return 0; }
【例题】蚯蚓
蛐蛐国最近蚯蚓成灾了！
隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有 n n n 只蚯蚓，第 i i i 只蚯蚓的长度为 a i a_i ai ，所有蚯蚓的长度都是非负整数，即可能存在长度为 0 0 0 的蚯蚓。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只，将其切成两段。
若有多只最长的，则任选一只。
神刀手切开蚯蚓的位置由有理数 p p p 决定。
一只长度为 x x x 的蚯蚓会被切成两只长度分别为 ⌊ p x ⌋ lfloor px rfloor ⌊px⌋ 和 x − ⌊ p x ⌋ x−lfloor pxrfloor x−⌊px⌋ 的蚯蚓。
特殊地，如果这两个数的其中一个等于 0 0 0，则这个长度为 0 0 0 的蚯蚓也会被保留。
此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加一个非负整数 q q q。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。
蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 m m m 秒才能到来。
蛐蛐国王希望知道这 m m m 秒内的战况。
具体来说，他希望知道：
m
m
m 秒内，每一秒被切断的蚯蚓被切断前的长度，共有
m
m
m 个数。
m
m
m 秒后，所有蚯蚓的长度，共有
n
+
m
n+m
n+m 个数。
数据范围
1
≤
n
≤
1
0
5
,
0
≤
a
i
≤
1
0
8
,
0
<
p
<
1
,
0
≤
q
≤
200
,
0
≤
m
≤
7
×
1
0
6
,
0
<
u
<
v
≤
1
0
9
,
1
≤
t
≤
71
1≤n≤10^5, 0≤a_i≤10^8, 0<p<1,\ 0≤q≤200, 0≤m≤7times10^6, 0<u<v≤10^9,\ 1≤t≤71
1≤n≤105,0≤ai≤108,0<p<1,0≤q≤200,0≤m≤7×106,0<u<v≤109,1≤t≤71
分析：
将题目问题抽象一下，就是对于一个集合，每次操作是取出集合中最大的元素，然后将其分解为 ⌊ p x ⌋ lfloor px rfloor ⌊px⌋ 和 x − ⌊ p x ⌋ x−lfloor pxrfloor x−⌊px⌋ ，然后其它元素增大 q q q ，刚刚分解的两个元素又放入队列，在这 m m m 次操作过程中，每 t t t 次输出当前所有蚯蚓的长度，然后再最后一次执行完后再输出所有蚯蚓的长度。
对于集合中动态快速的取出最大值这个操作可以使用堆优化，而因为会其他长度会动态的变化，所以采取一种等价的操作，即与其其它元素增大，不如新来的元素减小，所以有了下面的算法：
使用一个变量 d e l t a delta delta 表示增大量，集合中的数值加上它就是真实的数值，对于每一次操作：
- 取出集合最大值 x x x ，令 x = x + d e l t a x = x + delta x=x+delta ；
- 把 ⌊ p x ⌋ − d e l t a − q lfloor px rfloor -delta-q ⌊px⌋−delta−q 和 x − ⌊ p x ⌋ − q x - lfloor px rfloor - q x−⌊px⌋−q 插入集合；
- 令 d e l t a = d e l t a + q delta = delta + q delta=delta+q 。
此算法的时间复杂度为 O ( m l o g ( n ) ) O(mlog(n)) O(mlog(n)) ，虽然已经很好了，但是对于这道题题目不过，所以必须的是 O ( m ) O(m) O(m) 的时间复杂度，因此得试图找出其中是否有单调性。
对于 p , q p,q p,q 是固定常数， 0 < p < 1 0<p < 1 0<p<1 且 q q q 是非负整数。设 x 1 , x 2 x_1,x_2 x1,x2 为非负整数，当 x 1 ≥ x 2 x_1 ge x_2 x1≥x2 时，有 ⌊ p x 1 ⌋ + q = ⌊ p x 1 + q ⌋ ≥ ⌊ p x 2 + p q ⌋ = ⌊ p ( x 2 + q ) ⌋ lfloor px_1 rfloor + q = lfloor px_1 + q rfloorge lfloor px_2 + pq rfloor= lfloor p(x_2 + q) rfloor ⌊px1⌋+q=⌊px1+q⌋≥⌊px2+pq⌋=⌊p(x2+q)⌋ 。所以如果 x 1 x1 x1 先取出，它所分解的元素 ⌊ p x 1 ⌋ lfloor px_1 rfloor ⌊px1⌋ 始终大于后取出的元素 ⌊ p ( x 2 + q ) ⌋ lfloor p(x_2+q) rfloor ⌊p(x2+q)⌋。
同理分析 x − ⌊ p x ⌋ x-lfloor pxrfloor x−⌊px⌋ 也是同样的结论，所以我们得出结论，原本的元素、分解元素 1 1 1 和分解元素 2 2 2 它们各自具有单调性，每次操作我们只需要在这三种中选出最大的元素，然后分解后放入各自的队尾，这样就是线性的算法了。
代码如下：
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
68
69
70
71
72
73
74
75#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e5 + 5; const int INF = 0x3f3f3f3f; LL n,m,q,u,v,t; double p; queue<LL> A, B, C; LL a[N]; int get_m(LL &x) { x = max({A.empty()? - INF :A.front(),B.empty()?-INF:B.front(), C.empty()?-INF:C.front()}); if(!A.empty() && x == A.front()) { A.pop(); return 1; } if(!B.empty() && x == B.front()) { B.pop(); return 2; } if(!C.empty() && x == C.front()) { C.pop(); return 3; } return 4; } int main() { scanf("%lld%lld%lld%lld%lld%lld", &n, &m, &q, &u, &v, &t); p = u * 1.0 / v; for(int i = 0; i < n; ++i) { scanf("%lld", &a[i]); } sort(a, a + n); reverse(a, a + n); for(int i = 0; i < n; ++i) A.push(a[i]); LL delta = 0; for(int i = 1; i <= m; ++i) { LL x; get_m(x); x += delta; if(i % t == 0) printf("%lld ", x); B.push(LL(p * x) - delta - q); C.push(x - LL(p * x) - delta - q); delta += q; } puts(""); for(int i = 1; i <= (m + n); ++i) { LL x; get_m(x); if(i % t == 0) printf("%lld ", x + delta); } return 0; }
【例题】双端队列
达达现在碰到了一个棘手的问题，有 N N N 个整数需要排序。
达达手头能用的工具就是若干个双端队列。
她从 1 1 1 到 N N N 需要依次处理这 N N N 个数，对于每个数，达达能做以下两件事：
-
新建一个双端队列，并将当前数作为这个队列中的唯一的数；
-
将当前数放入已有的队列的头之前或者尾之后。
对所有的数处理完成之后，达达将这些队列按一定的顺序连接起来后就可以得到一个非降的序列。
请你求出最少需要多少个双端序列。
分析：
直接模拟显然很难，但是这 N N N 个数总会被分成放入各个双端队列，如果能发现一个结论可以得出那些数会在一个双端队列中就很好回答问题了。
直观的想，一个双端队列放入的序列肯定也要有序。我们把原序列的位置与它上面的数字对应，即对于序列 [ 3 , 6 , 0 , 9 , 6 , 3 ] [3,6,0,9,6,3] [3,6,0,9,6,3] ，下标分别是 [ 1 , 2 , 3 , 4 , 5 ] [1,2,3,4,5] [1,2,3,4,5] 。排序后 [ 0 , 3 , 3 , 6 , 6 , 9 ] [0,3,3,6,6,9] [0,3,3,6,6,9] ，原序列的下标就变成了 [ 3 , 1 , 6 , 2 , 5 , 4 ] [3,1,6,2,5,4] [3,1,6,2,5,4] 。
要做到双端队列有序，那么 它的放入下标顺序一定是满足单谷性质，即先单调递减，后单调递增。不过因为元素中存在相同的所以这些下标可以进行交换，即 [ 0 , [ 3 , 3 ] , [ 6 , 6 ] , 9 ] [0,[3,3],[6,6],9] [0,[3,3],[6,6],9] ， [ 3 , [ 1 , 6 ] , [ 2 , 5 ] , 4 ] [3,[1,6],[2,5],4] [3,[1,6],[2,5],4] 。
因此问题就变为了，如果调整这些相同元素的下标，使得单谷更少。
这里我比较推荐画图推理，我就不推理了。
代码如下：
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#include <bits/stdc++.h> using namespace std; typedef pair<int, int> PII; const int INF = 0x3f3f3f3f; const int N = 200010; struct Node { int id; int v; bool operator < (const Node &W) const { if(v == W.v) return id < W.id; return v < W.v; } } a[N]; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%d", &a[i].v); a[i].id = i; } sort(a + 1, a + 1 + n); a[0] = {0, INF}; int res = 1, last = INF, dir = -1; for(int i = 1; i <= n;) { int j = i; while(j <= n && a[j].v == a[i].v) j++; int v = a[i].v, min_e = a[i].id, max_e = a[j - 1].id; if(dir == -1) { if(last > max_e) last = min_e; else dir = 1, last = max_e; } else { if(last < min_e) last = max_e; else { res++; dir = -1; last = min_e; } } i = j; } cout << res ; return 0; }
单调队列
【例题】最大子序和
输入一个长度为 n n n 的整数序列，从中找出一段长度不超过 m m m 的连续子序列，使得子序列中所有数的和最大。
注意： 子序列的长度至少是 1 1 1。
数据范围
1
≤
n
,
m
≤
300000
1le n,mle 300000
1≤n,m≤300000
分析：
我们设 S i j S_{ij} Sij 表示为在序列中 i i i 到 j j j 得所有元素之和，如果我们固定了 j j j 的值，那么 S i j S_{ij} Sij 要最大就等同于找出 min i ∈ [ j − m + 1 , j − 1 ] ( S 1 i ) min_{iin[j-m + 1,j-1]}(S_{1i}) mini∈[j−m+1,j−1](S1i)，而这就是单调队列的模型—滑动窗口。
代码如下：
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#include <bits/stdc++.h> using namespace std; int main() { int n, m; scanf("%d%d", &n, &m); vector<int> a(n + 1); a[0] = 0; for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); a[i] += a[i - 1]; } deque<int> que; que.push_back(0); int ans = - 0x3f3f3f3f; for(int i = 1; i <= n; ++i) { while(que.size() && que.front() < i - m) que.pop_front(); ans = max(ans, a[i] - a[que.front()]); while(que.size() && a[que.back()] >= a[i]) que.pop_back(); que.push_back(i); } cout << ans ; return 0; }
最后
以上就是漂亮发带最近收集整理的关于基础数据结构 -队列单调队列的全部内容，更多相关基础数据结构内容请搜索靠谱客的其他文章。
发表评论 取消回复