AcWing 467. 海港
原题链接
简单
作者:
若雨
,
2023-11-14 17:23:32
,
所有人可见
,
阅读 55
由于时间单调递增,队列满足严格单调的特性,只需维护一个窗口,满足队尾与队头之间的时间间隔小于24小时;
如何更新窗口中的国籍数量?桶排序的思想:ans记录国籍数量,cnt[i]表示国籍i的人数;
元素入队时,若国籍i未记录,则ans ++,此外cnt[i] ++;
元素出队时,cnt[i] --,若国籍i人数为空 ans --;
记录 乘客到达海港的时刻 以及 对应的国籍 --> 结构体队列,每个船只的每个乘客为一个元素
#include <cstdio>
#define limit_t 86400
const int N = 1e5 + 5;
struct info {
int t, s;
} q[3 * N];
int hh = 0, tt = -1;
int cnt[N], ans;
int main() {
int n; scanf("%d", &n);
while (n --) {
int cur_t, num; scanf("%d%d", &cur_t, &num);
// 出队
while (hh <= tt && cur_t - q[hh].t >= limit_t) {
cnt[q[hh].s] --;
if (cnt[q[hh].s] == 0) ans --;
hh ++;
}
// 入队
while (num --) {
int x; scanf("%d", &x);
if (cnt[x] == 0) ans ++;
cnt[x] ++;
q[++ tt] = { cur_t, x };
}
printf("%d\n", ans);
}
return 0;
}