2016NOIP普及组真题 3. 海港

线上OJ：

一本通：http://ybt.ssoier.cn:8088/problem_show.php?pid=1975
洛谷：https://www.luogu.com.cn/problem/P2058

核心思想：

1. 题目中明确表示 “保证输入的 ti 是递增的”，故给到的船入港信息不需要排序，可以直接使用

2. 由于题目的数据量较大（有 $10^5$ 艘船，每艘船上有 $10^5$ 个人），故在每次读入新的船入港信息时，应该考虑 对船 进行 出队入队 操作（$10^5$次），而 不是对船上的人 进行出队入队操作（$10^{10}$次）。 如果 对人 进行队列操作，会有 30% 数据 超时。

注：本题一本通的数据比较强。如果在洛谷上，对人进行出入队操作也能过。

以下为 第 i 艘船入港时的操作流程图

题解代码：

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;

int n, ans;	// ans为最终输出结果，即来自多少个国家
struct node
{
    int t, k, id; // t：船进入港口的时间，k：该船上有k个人，id：这艘船的序号
};

int cnt[MAXN]; // cnt[i] 表示第i个国家的累计人数
vector<int> g[MAXN];	// g[i][j] 表示第 i 艘船上第 j 个人的国籍。这里要开 vector
queue<node> q;

int main()
{
    scanf("%d", &n); 
    int t, k, x;
    for(int i = 1; i <= n; i++)		
    {
        scanf("%d%d", &t, &k);
        q.push({t, k, i}); // 将船的信息入队，而不是将人的信息入队
        
        // 当有新轮船入港时，第一步：先把 86400 秒以前的无用信息剔除
        while(!q.empty() && (t - q.front().t >= 86400) )
        {
            node p = q.front();   // 则取出队首船的信息，
            for(int j = 0; j < p.k; j++)       
            {	// 将第 g[p.id] 艘船上的国籍信息逐一删除，如果该国家仅剩一人，则清零后总国家数量--
                if( cnt[ g[p.id][j] ] == 1) 
                    ans--;
                cnt[ g[p.id][j] ]--;
            }
            q.pop();   // 该艘船出队列         
        }
        
        // 第二步：把新轮船的信息加入g[i] 的数组
        for(int j = 1; j <= k; j++)
        {
            scanf("%d", &x);
            g[i].push_back(x); // 将读入的国籍信息追加在第i艘船的 g[i] vector 后
            if( cnt[x] == 0 )
                ans++;
            cnt[x]++;
        }
        printf("%d\n",ans);
    }
    return 0;
}