题解 P2058 【海港】
超级详细题解（打了6小时，求点赞啊！！！）
首先来讲讲队列和优先队列（非常详细！！！）
然后再对题目进行分析，附上代码。
关于队列
队列其实就是一种数据结构 “栈”无需自己写,递归过程中会自动开系统栈 “队列”需要自己写,一般有两种方式:
- 用数组模拟实现队列
- 用STL中自带的queue(常数比priority_queue大很多,慎用)
① 数组模拟队列
定义 int que[100],L = 1,R =0;
队列不空 while(L<=R)
新元素入队 que[++R] = i;
取队首元素并出队
int cur = que[L++];
②自带STL queue
定义 queue<int> q;
队列不空 while(!q.empty())
新元素入队 q.push(m);
取队首元素 q.front();
队首元素出队 q.pop();
③结构体队列 //图片转自CSDN
我们可以看出用法还是差不多的，只是将整形换成自己定义的结构体一样。
说人话，就是把int换成结构体！！！
④优先队列
定义：说人话就是用个东西把一群元素排队（默认从大到小，可更改为从小到大）
库： #include<queue>
定义队列：
priority_queue<int(或其他类型)> q
priority_queue<int,vector<int>,greater<int>> q(队列从小到大排序)
基本操作： (其中q为定义的队列)注意它没有队列的q.back()
①q.push（x） x为定义的变量，将x压进队列
②q.top（） 返回队列第一个元素
③q.pop（） 删除队列第一个元素
④q.size（） 返回队内元素数量
⑤q.empty() 判断队列是否空，空则返回1，否则返回0；
那么学会了以后我们来做个测试吧！
| 输入输出 | |
|---|---|
| 输入 ：10 11 5 78 | |
| 输出 ： 5 10 11 78 |
总结：优先队列相当与动态的数组（自动帮你排序）所以对于要遍历时时更新元素的情况下，用优先队列会方便很多
既然学了优先队列，那么还是建议大家去水水合并果子
传送门
算法介绍结束！！！
下面来分析题目
首先看到这里，我们首先的思路是开个结构体。
从第一个船开始遍历找到这个船24小时内进港的船，再统计国籍数，输出，进行下一波遍历。
那么问题就来了，我们如果记录每个状态可能会爆内存。（算内存应该都会吧）我们能否对这个算法进行优化呢？？？
-
优化①： 在读入时我们即可记录下每个船的人的国籍（去重），这样只要记下人头数就行了（无需记船了）。
-
优化②： 将每艘船上的人的到达时间和国籍记录下来，把结构体放进一个队列中。由于是比较之前的，所以边读一次输出一次就免得重新遍历了。
但是细细一想。这群人来的批数有用吗？？？
我们也许只要开个结构体存人头数（这个人来的时间和这个人的所属国籍）不就行了嘛？？？
那么问题就很好办了。
我们的思路是：
先读进人数，再读进每个人的国籍，把人到来的时间和国籍放进队列。去重计数（因为对答案没贡献）。
其次，队列并不要记录每个结构体，它只要记住主时间线之前24小时内的结构体即可。
所以我们先全记下来，再判重，之后再进行队列和答案的更新，最后输出答案即可（答案其实不用清零，因为之前的答案有可能会对现在的做贡献，这样就不用每次读入都遍历了）
详细分析
#include<cstdio>
#include<queue>
#define rei register int
using namespace std;
int n, t, m, x;
int temp_nation[1000005];
int ans;
struct node
{
int s, t;
//made in china
};
queue<node>ship;
node h;
int main()
{
scanf("%d",&n);
for(rei i=1;i<=n;i++)
{
scanf("%d%d",&t,&m);
while(!ship.empty())//只要还有人就对队列进行检查
{
h = ship.front();//循环取队头（由于时间是单调递增的）
if(h.t+86400<=t)//如果在时间外（不符合条件），则对答案和队列进行更新（删减）
{
temp_nation[h.s]--;//这个国籍人数总数减1（因为这不是24小时内的人）
if(temp_nation[h.s]==0) ans--;//如果这个国籍没有人了，则答案数减1（之前记过）
ship.pop();//把这个被时代所淘汰的人给丢掉
continue;//因为是单调递增的，所以有可能还会有，继续去找
}
break;//如果现在这个在24小时内，后面的肯定也符合条件，直接退出
}
for(rei j=1;j<=m;++j) //查完前面后，我们就对这只本身的船进行统计
{
scanf("%d",&x);//输入国籍
h.s = x, h.t = t;//存进结构体
ship.push(h);//把这个人（结构体）给存进队列
temp_nation[x]++;//这个国籍的人加1（桶排思想）
if(temp_nation[x]==1) ans++;//如果这个国籍是！相对！第一次出现，那么就算上他
}
printf("%d\n",ans);//模拟完了以后就输出答案
}
return 0;
}