原题链接
与其说入港的是船,不如说入港的是不同的“国家”。
那么题目就很简单了:维护一个关于不同进港国家的时间队列。
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;}
