【洛谷】队列相关经典算法题详解：模板队列、机器翻译、海港

---

【模板】队列

题目描述

题目解析

本题非常简单，小编这里用数组模拟队列实现，需要两个下标分别标记队头和队尾。

代码

using namespace std;
#include <iostream>const int N = 1e6 + 10;
int qe[N];
int head = 0; //标记队头下标
int tail = 0; //标记队尾下标int main()
{int n;cin >> n;int a, b;while (n--){cin >> a;if (a == 1){//队尾插入cin >> b;qe[tail++] = b;}else if (a == 2){if (head == tail){//队列为空cout << "ERR_CANNOT_POP" << endl;}else{++head;}}else if (a == 3){if (head == tail){//队列为空cout << "ERR_CANNOT_QUERY" << endl;}else{cout << qe[head] << endl;}}else{cout << tail - head << endl;}}return 0;
}

机器翻译

题目描述

题目解析

本题重在理解题意，内存的处理数据逻辑是先进先出，所以可以用一个队列来模拟内存。因为stl的队列不支持下标随机访问，所以需要开辟一个st数组用来映射标记队列中存放的数字。变量count记录查找词典次数，也就是数据入队列次数，遍历所有数字，若遇到的数字在队列中存在，则不做任何操作继续遍历，若遇到的数字在队列中不存在，则需要把数字入队列，并把当前数字对应st数组的下标置为true，若此时队列已经满了，还需要把队列pop一下，并把pop掉元素的数值对应st数组的下标置为false。最后输出count结果。

代码

using namespace std;
#include <iostream>
#include <queue>const int M = 1010;
//一个下标映射数组，标记某个值是否在队列中
bool st[M]; int main()
{int m, n;cin >> m >> n;queue<int> q;int x = 0; //暂存插入数据int count = 0; //标记插入队列次数while (n--){cin >> x;//队列中没有x则插入xif (st[x] == false){++count;//队列空间不足，pop一个数据后再插入数据if (q.size() >= m){//pop同时把映射数组对应位置置为falsest[q.front()] = false; q.pop();}//队列空间足够，直接插入数据q.push(x);st[x] = true;}}cout << count;return 0;
}

海港

题目描述

题目解析

本题有一定难度，厘清思路还是很简单的。首先题目的信息很多，时间，船，人，国籍，我们最后要输出的是一定时间范围内有多少种国籍，而国家默认和人绑定，所以船只是一个载体，最主要要统计时间和人的信息，所以我们可以用一个pair手动将人和时间绑定。
根据题目描述一个国家有多少人是不确定的，所以可以用一个数组ctarr来统计某个国家的人数，数组下标代表国家，数组元素代表国家人数。
本题题意是以新来一艘船的时间为基准，统计离该时间最近的24小时内的国籍信息，也就是若船是在该时间24小时之前或者更早来的就不在统计范围内，要把这些数据去掉，并且时间是一直递增的，所以符合队列的先进先出原则，可以用队列来存储人和时间绑定的pair信息。
准备工作做完了，开始按船为单位读入数据，还需要用一个kind维护国籍信息。来一个人，就把它的时间和国籍打包存进queue，并把ctarr对应国籍加一，如果对应国籍元素是0，说明该人是当前时间范围内第一个该国籍的人，需要把kind加一。
读完一艘船的信息后，我们需要让队列合法，也就是清除在时间范围外的数据。遍历每一个在时间范围外的人，把该人ctarr对应国籍减一，如果对应国籍元素是1，需要把kind减一。最后输出kind信息。

代码

using namespace std;
#include <iostream>
#include <queue>typedef pair<int, int> PII;const int N = 1e5 + 10;
//int st[N];
int ctarr[N];   //ctarr[i]表示i国家一共有多少人
int kind = 0;   //国家种类个数int main()
{//queue存储每个人的信息,将人的信息和时间绑定//pair<人到港时间， 人国籍>queue<PII> q;//n艘船，船到达时间为t,船上有m个人,该人的国籍为kint n, t, m, k; cin >> n;for (int i = 0; i < n; i++){cin >> t >> m;//遍历整艘船乘客for (int j = 0; j < m; j++){cin >> k;q.push({ t, k }); //将人的信息插入队列//ctarr某个下标从0到1，国家种类个数加1if (ctarr[k] == 0)++kind;++ctarr[k]; //对应国籍人数加1}//让队列合法(队尾入，队头出，队尾-队头)while (q.back().first - q.front().first >= 86400){pair<int, int> tmp = q.front();q.pop();//ctarr某个下标从1到0，国家种类个数减1if (ctarr[tmp.second] == 1)--kind;--ctarr[tmp.second];}cout << kind << endl;}return 0;
}

以上就是小编分享的全部内容了，如果觉得不错还请留下免费的关注和收藏
如果有建议欢迎通过评论区或私信留言，感谢您的大力支持。
一键三连好运连连哦~~