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

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

文章目录

• 前言
• 一、海港
  • 1.1题目
  • 1.2算法原理
  • 1.3代码
• 总结与每日励志

前言

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

一、海港

1.1题目

链接：海港

1.2算法原理

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

1.3代码

#include<iostream>#include<queue> using namespace std;constint N =1e5+10;typedef pair<int,int> PII;//人从哪艘船来属哪国 queue<PII> q;int st[N];//不同国籍的人数int kind;//国籍种类intmain(){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;}return0;}

总结与每日励志

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