队列
一、单调队列
单调队列通常配合双端队列（deque）实现，维护单调性并支持快速的插入、删除。
- 定义：单调队列是一种队列，队列中的元素按某种单调性排序（递增或递减），并支持在队头获取最大或最小值的操作。
- 入队元素比队列中的大，弹出所有
- 入队元素比队列中的小，加入队列
- 队列长度是一个窗口
| 模板 |
|---|
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, k;
struct node {
int pos, num;
};
deque<node> dq;
int main() {
cin >> n >> k; // n个数，窗口大小为k
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
/* 元素下标不在窗口内 → 从头上弹出 */
if (!dq.empty() && (dq.front().pos < i - (k - 1))) {
dq.pop_front();
}
/* 入队元素比队尾元素大 → 从尾部弹出 */
while (!dq.empty() && (dq.back().num <= a[i])) {
dq.pop_back();
}
/* 入队 */
dq.push_back({i, a[i]});
if (i >= k) {
cout << dq.back().num << " ";
}
}
}
|
例题
e.g. 约瑟夫问题
题目描述
\(n\) 个人围成一圈，从第一个人开始报数,数到 \(m\) 的人出列，再由下一个人重新从 \(1\) 开始报数，数到 \(m\) 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。
输入格式
输入两个整数 \(n,m\)。
输出格式
输出一行 \(n\) 个整数，按顺序输出每个出圈人的编号。
样例
样例输入
样例输出
提示
\(1 \le m, n \le 100\)
| #include<bits/stdc++.h>
using namespace std;
int main() {
int n, m; // n是人数，m是报数到几出列
cin >> n >> m;
queue<int> q; // 创建队列模拟圆圈中的人
for (int i = 1; i <= n; i++) { // 将1到n的数字放入队列
q.push(i); // 数字代表每个人的编号
}
for (int i = 1; i <= n; i++) { // 一共要出列n个人
for (int j = 1; j < m; j++) { // 每次报数到m-1
int f = q.front(); // 取出队首的人
q.pop(); // 移除队首
q.push(f); // 将这个人放到队尾(因为没报到m，不用出列)
}
cout << q.front() << ' '; // 输出报数为m的人(即出列的人)
q.pop(); // 移除这个人(出列)
}
}
|
\[ 用数学方法\\ f(n,k)=(f(n−1,k)+k)\mod n \]
| #include <iostream>
using namespace std;
int josephus(int n, int k) {
if (n == 1) return 0;
return (josephus(n - 1, k) + k) % n;
}
int main() {
int n, k;
cin >> n >> k;
int result = josephus(n, k);
cout << result + 1 << ' '; // 输出结果加1，因为题目中的位置是从1开始的
return 0;
}
|
e.g. [NOIP2010 提高组] 机器翻译
题目背景
NOIP2010 提高组 T1
题目描述
小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。
这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。
假设内存中有 \(M\) 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 \(M-1\)，软件会将新单词存入一个未使用的内存单元；若内存中已存入 \(M\) 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
假设一篇英语文章的长度为 \(N\) 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。
输入格式
共 \(2\) 行。每行中两个数之间用一个空格隔开。
第一行为两个正整数 \(M,N\)，代表内存容量和文章的长度。
第二行为 \(N\) 个非负整数，按照文章的顺序，每个数（大小不超过 \(1000\)）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。
输出格式
一个整数，为软件需要查词典的次数。
样例
样例输入
样例输出
提示
样例解释
整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：
1：查找单词 1 并调入内存。1 2：查找单词 2 并调入内存。1 2：在内存中找到单词 1。1 2 5：查找单词 5 并调入内存。2 5 4：查找单词 4 并调入内存替代单词 1。2 5 4：在内存中找到单词 4。5 4 1：查找单词 1 并调入内存替代单词 2。
共计查了 \(5\) 次词典。
数据范围
- 对于 \(10\%\) 的数据有 \(M=1\)，\(N \leq 5\)；
- 对于 \(100\%\) 的数据有 \(1 \leq M \leq 100\)，\(1 \leq N \leq 1000\)。
| #include<bits/stdc++.h>
using namespace std;
int main() {
int M, N;
cin >> M >> N;
int count = 0;
queue<int> Q; // 创建队列Q
set<int> seen; // 创建集合seen，用于快速判断某个数是否在缓存中
for (int i = 0; i < N; i++) {
if (seen.find(i) == seen.end()) { // 如果数字i不在seen集合中
// seen.find()返回迭代器，如果找不到返回seen.end()
Q.push(i); // 将i加入队列
seen.insert(i); // 将i加入seen集合
count++; // 缓存未命中次数加1
}
if (Q.size() > M) { // 如果队列大小超过了限制M
int removed = Q.front(); // 获取队列最前面的元素
Q.pop(); // 从队列中移除这个元素
seen.erase(removed); // 从seen集合中也移除这个元素
}
}
cout << count;
return 0;
}
|
e.g. 求m区间内的最小值
题目描述
一个含有 \(n\) 项的数列，求出每一项前的 \(m\) 个数到它这个区间内的最小值。若前面的数不足 \(m\) 项则从第 \(1\) 个数开始，若前面没有数则输出 \(0\)。
输入格式
第一行两个整数，分别表示 \(n\)，\(m\)。
第二行，\(n\) 个正整数，为所给定的数列 \(a_i\)。
输出格式
\(n\) 行，每行一个整数，第 \(i\) 个数为序列中 \(a_i\) 之前 \(m\) 个数的最小值。
输入输出样例
输入
输出
说明/提示
对于 \(100\%\) 的数据，保证 \(1\le m\le n\le2\times10^6\)，\(1\le a_i\le3\times10^7\)。
| #include <bits/stdc++.h>
using namespace std;
struct node {
int pos, num;
};
deque<node> dq;
int main() {
int n, m;
int a[2000005];
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cout << 0 << "\n";
for (int i = 1; i < n; i++) {
if (!dq.empty() && dq.front().pos == i - m)
dq.pop_front();
while (!dq.empty() && dq.back().num >= a[i])
dq.pop_back();
dq.push_back((node){i, a[i]});
cout << dq.front().num << "\n";
}
}
|