题目描述
小 K 是一个海港的海关工作人员,每天都有许多船只到达海港,船上通常有很多来自不同国家的乘客。
小 K 对这些到达海港的船只非常感兴趣,他按照时间记录下了到达海港的每一艘船只情况:
对于第 $i$ 艘到达的船,他记录了这艘船到达的时间 $t_i$(单位:秒),船上的乘客数量 $k_i$ ,以及每名乘客的国籍 $x_{i,1},x_{i,2},…,x_{i,k_i}$ 。
小 K 统计了 n 艘船的信息,希望你帮忙计算出以每一艘船到达时间为止的24小时(24小时=86400秒)内所有乘船到达的乘客来自多少个不同的国家。
形式化地讲,你需要计算 n 条信息。
对于输出的第 i 条信息,你需要统计满足 $t_i−86400<t_p≤t_i$ 的船只 p ,在所有的$x_{p,j}$中,总共有多少个不同的数。
输入格式
第一行输入一个正整数 n ,表示小 K 统计了 n 艘船的信息。
接下来 n 行,每行描述一艘船的信息:前两个整数 ti 和 ki 分别表示这艘船到达海港的时间和船上的乘客数量,接下来 $k_i$ 个整数 $x_{i,j}$ 表示船上乘客的国籍。
保证输入的 $t_i$ 是递增的,单位是秒;表示从小 K 第一次上班开始计时,这艘船在第 $t_i$ 秒到达海港。
输出格式
输出 n 行,第 i 行输出一个整数表示第 i 艘船到达后的统计信息。
数据范围
$1≤n≤10^5$,
$∑k_i≤3∗10^5$,
$1≤x_i,j≤10^5$,
$1≤t_i≤10^9$
输入样例
3
1 4 4 1 2 2
2 2 2 3
10 1 3
输出样例
3
4
4
算法思想(滑动窗口+桶排序)
- 题目提示保证输入的 $t_i$ 是递增的,因此可以使用滑动窗口的思想,将到港的乘客按照时间顺序依次入队。在入队之前,将队首所有已经超过86400秒的乘客出队。
- 在入队和出队的同时,统计不同国籍的乘客人数。可以使用桶排序的思想,以国籍作为键、以乘客数量为值保存到数组中:
- 每次出队,将该国籍的人数减少一个。如果该国籍的人数为0,则总国籍数量减少一个
- 每次入队,将该国籍的人数增加一个。如果增加之前,该国籍的人数为0,则总国籍数量增加一个
时间复杂度
$O(n\times k)$
代码实现
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 300010;
int q[N][2]; //循环队列,q[i][0]保存时刻,q[i][1]保存国籍
LL cnt[N]; //每个国籍的人数
int main()
{
int n;
scanf("%d", &n);
int hh = 0, tt = 0; //循环队列,tt指向队尾元素的下一个位置
int ans = 0;
while(n --)
{
int t, k;
scanf("%d%d", &t, &k);
//注意,这里是>= 86400,不包含第24小时这个时刻
while(hh != tt && t - q[hh][0] >= 86400)
{
int nation = q[hh][1];
cnt[nation] --;
if(cnt[nation] == 0) ans --;
hh ++;
if(hh == N) hh = 0;
}
for(int i = 1; i <= k; i ++)
{
int x;
scanf("%d", &x);
if(cnt[x] == 0) ans ++;
cnt[x] ++;
q[tt][0] = t, q[tt][1] = x;
tt ++;
if(tt == N) tt = 0;
}
cout << ans << endl;
}
return 0;
}
$997ms$
$423ms$
题目中有写,所有k相加不会超过3e5,所以存储的时候直接用队列即可;另外,假设数据量给的超过数组的所有空间,且时间一直没有超过24小时,那么使用循环数组会造成数据覆盖,导致最总的答案出错。
tql
妙啊
大佬,if(tt=N) tt=0 与if(hh=N) hh=0是什么意思啊???
循环队列,如果到了数组的末尾,就从头来过
嗯嗯,明白了,谢谢大佬
$$\texttt{%%%%%%%%}$$
66666
。
Orz
膜拜大佬!