【算法通关指南：数据结构和算法篇 】队列相关算法题：3.海港

🔥小龙报：个人主页 🎬作者简介：C++研发，嵌入式，机器人方向学习者 ❄️个人专栏：《算法通关指南》 ✨ 永远相信美好的事情即将发生

前言

本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》 等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力***ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长***

一、海港

1.1题目

链接：海港

在这里插入图片描述

1.2算法原理

先来的乘客，在时间逐渐增大的时候会先出列。因此，可以用队列模拟整个过程。 • 队列里面存每⼀个乘客，需要 存储乘客的编号还有进队的时间（我们可以使用一个pair类型）； • 进队的时候，把队列里面时间差大于等于24 小时的全出队（这里要使循环因为队列里面好几个元素共同构成一条船的信息），然后统计队列里面国家的个数； • 需要额外创建⼀个数组来统计队列里面各个国家的人数，方便在进出队的时候，统计国家的个数。

1.3代码

#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII; //人从哪艘船来属哪国
queue<PII> q;
int st[N]; //不同国籍的人数
int kind;  //国籍种类
int main()
{
	int n;
	cin >> n;

	while (n--)
	{
		int t, k;
		cin >> t >> k;
		for (int i = 1; i <= k; i++)
		{
			int x;
			cin >> x;
			q.push({ t, x });
			if (st[x]++ == 0)
				kind++;

			while (q.back().first - q.front().first >= 86400)
			{
				int temp = q.front().second;
				q.pop();

				if (st[temp]-- == 1)
					kind--;
			}
		}
		cout << kind << endl;
	}

	return 0;
}

总结与每日励志

✨本文介绍了海港问题的算法实现，通过队列模拟乘客进出港过程。算法利用队列存储乘客编号和到达时间，并维护一个数组统计各国人数。当时间差超过24小时时，将相应乘客出队并更新国家种类数。代码简洁高效，适合处理实时统计需求。文章强调持续学习算法的重要性，鼓励读者保持积极心态，相信努力终有回报。