♐ CSP_J 组真题
2016年
3. 海港

线上OJ:

一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1975 (opens in a new tab)
洛谷:https://www.luogu.com.cn/problem/P2058 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/469/ (opens in a new tab)

核心思想:

  1. 题目中明确表示 “保证输入的 ti 是递增的”,故给到的船入港信息不需要排序,可以直接使用
💡
  1. 由于题目的数据量较大(有 10510^5 艘船,每艘船上有 10510^5 个人),故在每次读入新的船入港信息时,应该考虑 对船 进行 出队入队 操作(10510^5次),而 不是对船上的人 进行出队入队操作(101010^{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;
}