原题链接
与其说入港的是船,不如说入港的是不同的“国家”。
那么题目就很简单了:维护一个关于不同进港国家的时间队列。
qt保存进港时间,qc保存的是对应时间进港的国家编号。两个队列中的元素一一对应。
每当有若干元素要进队时(元素数量取决于新进港船只上人数),首先看看队首元素还是不是在待入队元素的“24h内”。如果不在了,那么对应的若干元素就得出队。qt中的元素直接出队即可,直到qt队首元素在待入队元素的“24h内”;qc中的元素出队时,记得在cnt计数数组中将对应下标的元素-1,如果-1之后相应元素变成了0,那么相应的答案也要-1。
之后待入队元素可以入队了。入队时记得cnt中对应元素+1。如果cnt中的对应元素原来是0,别忘了答案也要+1。
#include <iostream>
#include <deque>
using namespace std;
const int N = 100010, DAY_SEC = 86400;
int cnt[N] = {0, }, n, ans = 0;
deque<int> qt, qc;
int main(void)
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int t, k;
scanf("%d%d", &t, &k);
while (!qt.empty() && t - DAY_SEC >= qt.front())
{
int x = qc.front();
if (--cnt[x] == 0) ans--;
qt.pop_front();
qc.pop_front();
}
for (int j = 0; j < k; j++)
{
int x;
scanf("%d", &x);
qt.push_back(t);
qc.push_back(x);
if(++cnt[x] == 1) ans++;
}
printf("%d\n", ans);
}
return 0;
}