【题目链接】

ybt 1975：【16NOIP普及组】海港
洛谷 P2058 [NOIP2016 普及组] 海港

【题目考点】

1. 模拟

2. 队列

【解题思路】

解法1：设队列，每个人是队列中的一个元素

由于人数总和（即k的加和）最大为$3\ast 10^5$，可以把每个人作为一个元素保存在队列中。
设计数数组c，c[i]表示第i国籍的人数。
设结构体Peo表示一个人，每个人包含属性：时间time、国籍nation。
t时刻有船到岸：

• 先将队列中所有到达时间time比当前时间t早86400以上的人出队。每出队1个人，该国籍的人数减1。如果该国籍的人数变为0，则总国籍数量减1。
• 而后把该船上所有人加入到队列中，对于每个入队的人，这个人的国籍的人数加1。如果该国籍的人数从0变为1，则总国籍数量加1。

每次有船到岸，就输出一下国籍总数。

解法2：设队列，每条船是队列中的一个元素

每条船为一个元素，包含属性vector类型的nation，保存所有人的国籍，以及time表示时间。
注意：nation必须设为长度可变的vector，这样可以节省空间。如果设为数组，则会内存超限。
t时刻有船到岸：

• 先将队列中所有到达时间time比当前时间t早86400以上的船出队。每出队1条船，遍历该船上的所有人，每人对应的国籍人数减1。如果该国籍的人数变为0，则总国籍数量减1。
• 而后把该船加入到队列中，对于每个船上的人，这个人的国籍的人数加1。如果该国籍的人数从0变为1，则总国籍数量加1。

每次有船到岸，就输出一下国籍总数。

【题解代码】

解法1：使用队列，每个人是队列中的一个元素

#include <bits/stdc++.h>
using namespace std;
struct Peo
{int time, nation;Peo(){}Peo(int a, int b):time(a), nation(b){}
};
int c[100005];//c[i]：第i国籍人数 
int main()
{queue<Peo> que;int n, t, k, x, ct = 0;//ct：总国籍数 cin >> n;for(int i = 1; i <= n; ++i){cin >> t >> k;while(que.empty() == false && que.front().time <= t-86400)//只要队列不空 {//到港时间que.front().time比当前时间t早86400秒以上的人都出队 int nat = que.front().nation;if(--c[nat] == 0)//nat国籍的人数减1，如果该国籍人数为0 ct--;//总国籍数量减少 que.pop(); }for(int j = 1; j <= k; ++j){cin >> x;if(++c[x] == 1)//x国籍人数增加，如果从0变为1 ct++;//总国籍人数增加 que.push(Peo(t, x)); }cout << ct << endl;}return 0;
}

解法2：设队列，每条船是队列中的一个元素

#include <bits/stdc++.h>
using namespace std;
struct Ship
{int time;vector<int> nation;
};
int c[100005];//c[i]：第i国籍人数 
int main()
{queue<Ship> que;int n, t, k, x, ct = 0;//ct：总国籍数 cin >> n;for(int i = 1; i <= n; ++i){cin >> t >> k;while(que.empty() == false && que.front().time <= t-86400)//只要队列不空 {//到港时间que.front().time比当前时间t早86400秒以上的人都出队 for(int nat : que.front().nation){if(--c[nat] == 0)//nat国籍的人数减1，如果该国籍人数为0 ct--;//总国籍数量减少 	}que.pop(); }Ship ship;ship.time = t;for(int j = 1; j <= k; ++j){cin >> x;ship.nation.push_back(x);if(++c[x] == 1)//x国籍人数增加，如果从0变为1 ct++;//总国籍人数增加 }que.push(ship);cout << ct << endl;}return 0;
}