海港

题目描述

小  K  是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。

小  K  对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第  ii  艘到达的船，他记录了这艘船到达的时间  titi​（单位：秒），船上的乘客数量  kiki​ ，以及每名乘客的国籍  xi,1，xi,2，⋯，xi,kixi​,1，xi​,2，⋯，xi​,ki​ 。

小  K  统计了  nn  艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的  24  小时（24 小时 = 86400 秒）内所有乘船到达的乘客来自多少个不同的国家。

形式化地讲，你需要计算  nn  条信息。对于输出的第  ii  条信息，你需要统计满足  ti−86400＜tp＜=titi​−86400＜tp​＜=ti​  的船只  pp ，在所有的  xp,jxp​,j  中，总共有多少个不同的数。

输入描述

第一行输入一个正整数  nn ，表示小  K  统计了  nn  艘船的信息。

接下来  nn  行，每行描述一艘船的信息：前两个整数  titi​  和  kiki​  分别表示这艘船到达海港的时间和船上的乘客数量，接下来  kiki​ 个整数  xi,jxi​,j  表示船上乘客的国籍。

保证输入的  titi​  是递增的，单位是秒；表示从小  K  第一次上班开始计时，这艘船在第  titi​  秒到达海港。

保证   1≤n≤105，ki≥1 ，∑ki≤3×105 ， 1≤xi,j≤105 ，1≤ti−1＜ti≤1091≤n≤105，ki​≥1 ，∑ki≤3×105 ， 1≤xi​,j≤105 ，1≤ti​−1＜ti​≤109 。

其中  ∑ki∑ki​  表示所有的  kiki​  的和，∑ki = k1 + k2 + ⋯ + kn∑ki​ = k1​ + k2​ + ⋯ + kn​ 。

输出描述

输出  nn  行，第  ii  行输出一个整数表示第  ii  艘船到达后的统计信息。

输入输出样例

示例 1

输入

3
1 4 4 1 2 2
2 2 2 3
10 1 3

输出

3
4
4

示例 2

输入

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

输出

3
3
3
4

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 40  |  总提交次数: 62  |  通过率: 64.5%

难度: 中等   标签: 2016, 模拟, NOIP

🌊 C++ 海港国籍统计问题：滑动窗口算法详解

🔍 算法思路

​​核心思想​​：滑动窗口 + 哈希表 + 队列
​​关键点​​：利用队列维护 24 小时（86400 秒）内的乘客信息，用哈希表实时统计不同国籍数量。
​​算法流程​​：

1. ​​乘客入队​​：每艘船的乘客按 (到达时间, 国籍) 入队
2. ​​哈希表更新​​：若国籍首次出现，不同国家计数 ans++
3. ​​过期乘客出队​​：移除队首所有满足 时间 ≤ 当前时间 - 86400 的乘客
4. ​​更新国籍计数​​：若某国籍计数归零，ans--
5. ​​输出结果​​：当前船的 ans 即为不同国家数

⚙️C++ 完整代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAX_COUNTRY = 100005; // 国籍最大编号

struct Passenger {
    int t; // 到达时间（秒）
    int x; // 国籍
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加速输入输出

    int n;
    cin >> n;
    queue<Passenger> q; // 乘客队列
    int countryCount[MAX_COUNTRY] = {0}; // 国籍计数
    int ans = 0; // 当前不同国家数

    for (int i = 0; i < n; i++) {
        int t, k;
        cin >> t >> k;

        // 步骤1：当前船乘客入队
        for (int j = 0; j < k; j++) {
            int x;
            cin >> x;
            q.push({t, x}); // 入队
            
            // 步骤2：更新国籍计数
            if (countryCount[x] == 0) {
                ans++; // 新增国籍
            }
            countryCount[x]++;
        }

        // 步骤3：移除过期乘客（时间 ≤ t-86400）
        while (!q.empty() && q.front().t <= t - 86400) {
            Passenger p = q.front();
            q.pop();
            
            // 步骤4：更新国籍计数
            countryCount[p.x]--;
            if (countryCount[p.x] == 0) {
                ans--; // 国籍归零
            }
        }

        // 步骤5：输出结果
        cout << ans << endl;
    }
    return 0;
}

🔍 代码解析

1. ​​数据结构选择​​

   • queue<Passenger>：按时间顺序存储乘客（先进先出）
   • countryCount[]：数组哈希表，索引为国籍，值为该国籍乘客数
   • ans：动态维护当前窗口内不同国籍数

2. ​​关键操作​​

   • ​​入队更新​​：新乘客国籍若首次出现，ans 立即增加
   • ​​出队条件​​：队首时间 ≤ 当前时间 - 86400（包含等于边界）
   • ​​计数归零​​：移除乘客后若某国籍归零，ans 需减 1

3. ​​复杂度分析​​

   • 时间复杂度：O(∑kᵢ) ≈ 3×10⁵（每个乘客入队出队各一次）
   • 空间复杂度：O(∑kᵢ + MAX_COUNTRY) ≈ 4×10⁵ 字节

📊 实例验证

​​样例 1 输入​​：

3
1 4 4 1 2 2
2 2 2 3
10 1 3

​​执行过程​​：

时间点	操作	队列内容 (t,x)	ans	输出
t=1	入队(1,4)(1,1)(1,2)(1,2)	[(1,4),(1,1),(1,2),(1,2)]	3	3
t=2	入队(2,2)(2,3)	[(1,4),(1,1),...,(2,2),(2,3)]	4	4
t=10	入队(10,3)	[所有乘客 + (10,3)]	4	4

​​样例 2 输入​​：

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

​​关键节点​​：

• ​​t=86401 时​​：移除时间≤1 的乘客（第一艘船所有乘客）
• ​​t=86402 时​​：队首时间=3 > 2（86402-86400），无需移除

输出：3 3 3 4 ✅ 符合样例

⚠️ 注意事项

1. ​​边界条件​​

   • 时间等于 t_i - 86400 的乘客​​不包含​​在窗口内（需移除）
   • 国籍编号范围：1 ≤ x ≤ 10⁵，数组需开 100005
   • 总乘客数 ≤ 3×10⁵，队列最大长度 3×10⁵

2. ​​极端情况测试​​

   • ​​测试点1​​：n=1, k=3×10⁵（单船超大乘客量）→ 检查内存
   • ​​测试点2​​：t₁=0, tₙ=10⁹（时间跨度大）→ 移除操作效率
   • ​​测试点3​​：所有船乘客国籍相同 → 验证 ans 是否恒为 1
   • ​​测试点4​​：连续多艘船在 1 秒内到达 → 队列快速膨胀

3. ​​易错点​​

   • 未处理 ios::sync_with_stdio(false) 导致 TLE
   • 国籍计数归零时未更新 ans
   • 误用 t_i - 86400 ≤ t_p（应为严格大于）

⚡ 优化建议

1. ​​按船存储优化​​
   改用 queue<Ship> 存储整船信息，减少队列操作：

   struct Ship {
       int t;
       vector<int> passengers;
   };
   // 出队时整船移除

2. ​​提前移除过期乘客​​
   在入队前移除过期乘客，避免重复检查：

   while (!q.empty() && q.front().t <= t - 86400) {
       // 先移除过期乘客
   }
   for (/* 当前船乘客入队 */) {
       // 再入队新乘客
   }

3. ​​内存池预分配​​
   预分配乘客内存减少动态开销：

   vector<Passenger> pool(300000);
   int index = 0;
   q.push(&pool[index++]);

💡 总结

本题通过 ​​滑动窗口+哈希表​​ 的组合，高效处理时间区间内的国籍统计。关键点在于：

1. 队列维护时间窗口内乘客
2. 哈希表动态更新国籍计数
3. 边界条件精细处理