"海港"这道题，P2058，NOIP 2016 普及组第三题。第一次在考场上见到它时，我还以为是个普通的模拟题：一艘船一艘船地读，一个国籍一个国籍地数，完事。结果越写越不对劲，等反应过来的时候，代码已经被我改成了一个"每次暴力扫全窗口"的慢速版本，复杂度直接爆炸。
那年普及组的分数线我记得很清楚，就差这题的最后两个点。所以后来我刷洛谷，把这道题翻来覆去重做了好几遍，也带过好几个学弟学妹过这道题。它值得好好写一篇题解——不是因为难，而是因为它把"滑动窗口"这个看起来高大上的概念，藏在了一个特别生活化的场景里。你以为在考模拟，其实在考数据结构。
这篇文章我尽量按照自己完整思考过程来写：先讲清楚题目在说什么，再讲为什么朴素做法会挂，接着给出C++和Python两版可AC的完整代码，最后把我见过的高频错误和边界坑全部列出来。不管你是刚学队列的新手，还是准备复盘的竞赛生，按这个思路走一遍，应该都能把这道题彻底吃透。
1. 题目到底在说什么
1.1 题干还原与核心考点
先把题目用大白话复述一遍：有一串记录，按时间顺序给出海港每艘船到达的时刻，以及船上每个乘客来自哪个国家。要求输出每一个记录时刻，往前24小时（86400秒）内到达的所有乘客中，一共涉及多少个不同国家。
输入格式长这样：
6 1 2 1 2 2 3 3 4 5 3 1 6 86401 1 7 86402 1 1 86403 1 2第一行是记录数n，接下来n行，每行第一个数是该船的到达时间t（单位是秒，且严格递增），第二个数是船上人数k，后面跟着k个国籍编号。
输出就是每行一个整数：这艘船到达时刻，往前推86400秒这个时间窗口里，所有乘客一共来自多少个不同国家。
这道题的核心考点有三个：一是能不能看出这本质是一个滑动窗口问题；二是窗口内应该以"乘客"为单位还是以"船"为单位存储；三是怎么在出入队的过程中动态维护"不同国家数"，而不是每次都重新统计。
1.2 第一眼容易被骗的地方
我第一次做这道题的时候，下意识的想法是：把每条船的记录存下来，每来一条新船，就去遍历所有船，找出时间差不超过86400的，然后把它们的乘客国籍全部塞进一个set里数个数。
这个思路对不对？对。但复杂度呢？假如有n条记录，每条记录平均k个乘客，每次遍历前i条船，还要把窗口内所有乘客重新数一遍，最坏情况接近O(n^2)级别的总操作量，而且连空间都可能存不下所有乘客。普及组第三题，数据范围不会让你这么舒服地过去的。
还有一个更隐蔽的坑：很多人会想到用"船"为最小单位入队，队列里存船的到达时间和这艘船上的全部乘客信息。这样确实能少开不少空间，但问题是，当一艘船有一部分乘客已经超过24小时、另一部分乘客还没有超过24小时的时候，你怎么处理？总不能把一艘船拆开。所以正确的做法是：队列的每一个元素，都对应一个单独的乘客，包含两个字段：到达时间、国籍。这样滑窗的边界才能精确到秒。
1.3 数据范围与设计的约束
这道题的n最大可以到10万级别，所有乘客数量之和也能到几十万级别。国籍编号的范围我记得是10万以内。这些数字意味着：
- 用数组模拟队列或者直接用std::queue/deque都行，几十万量级完全扛得住。
- 用一个计数器数组cnt[x]来记录当前窗口内国籍x的乘客人数，开10万出头的长度就够了，但保险起见开大一些。
- 答案的最大值也就是窗口内乘客总数，用int就能存下，不需要long long。
数据规模决定了解法必须是O(总乘客数)级别的，每个乘客进出队各一次，总共常数次操作。这也是判断一个解法是否合格的最快标准：只要你的代码里出现了"遍历窗口内所有乘客重新统计"这类操作，基本就是超时预定。
2. 解题思路：滑动窗口是怎么一步步推出来的
2.1 从朴素思路到滑窗的思维跳跃
前面说了，朴素做法每次都把窗口内所有乘客重新数一遍，显然浪费。注意一个关键事实：相邻两次询问之间，窗口并不是完全重置的，它只发生了两件事——右边多了一些新乘客，左边少了一些旧乘客。
这就像排队打饭：你不需要每次重新数一遍队伍里所有人的脸，只需要记住"现在有多少人"，有人加入就加一，有人离开就减一。同理，我们维护一个变量ans表示当前窗口内不同国籍的数量。当一个新国籍的乘客第一次进入窗口时，ans加一；当某个国籍的最后一名乘客离开窗口时，ans减一。
至于窗口里具体有哪些乘客，用一个先进先出的队列来维护：时间到达的先后顺序本来就是入队顺序。这正好就是队列的语义。所有新的船到达，它的乘客从队尾入队；所有超过24小时的乘客，从队头出队。
这个思路推到这里，其实已经不需要什么高深的理论了。滑动窗口就是一个概念包装，本质就是"增量维护一个连续区间上的统计量"。
2.2 队列里到底存什么
这是整道题最关键的决策：队列元素的最小粒度必须是"乘客"，而不能是"船"。
为什么？看一个例子：
1 2 1 2 86399 2 1 3第二艘船在86399到达，86401时刻，第一艘船的乘客和第二艘船的乘客都在86400秒窗口内。但如果时间再往后走一点，假设第三艘船在90000到达，那么第一艘船的乘客已经超出窗口了，第二艘船的乘客还在窗口内（90000-86399=3601秒）。如果队列元素是"船"，你怎么把第一艘船从窗口里踢出去？你需要遍历这艘船的所有乘客，把他们的cnt减掉。这本身还可以接受，但更麻烦的是逻辑判断：窗口的左边界是动态的，一艘船里所有乘客的到达时间相同，所以整艘船要么全部在窗口内，要么全部超出。从这个角度看，存船似乎也说得通——只要当队首船的到达时间超出窗口时，把这艘船的所有乘客统一出队即可。
但问题来了：这样队列里一个元素还是一个"船"，而船上可能有很多乘客，后续为了统计需要，还得再开一个结构体存变长数组。代码写起来又绕又容易错。更重要的是，如果以船为单位，Python那种list套list的性能会很差；如果以乘客为单位，一辆船上的乘客虽然时间相同，但每个都是独立的队列元素，出队判断精确到人，逻辑一致性最强。
我个人的建议很明确：以乘客为单位。每个队列元素就是(time, country)两个字段，简单直接，不容易出bug。
2.3 动态维护答案的完整规则
假设我们用cnt[c]表示当前窗口内国籍c的乘客总数，ans表示当前窗口内不同国籍数量。规则只有两条：
入队时：
- 如果cnt[c]从0变成1，说明窗口里出现了新的国籍，ans加1。
- 无论如何，cnt[c]自增1。
出队时：
- cnt[c]自减1。
- 如果cnt[c]从1变成0，说明这个国籍在窗口里一个乘客都没有了，ans减1。
这两条规则在每次遍历完一艘船的乘客后，以及清理完超时乘客后，都要保证正确。
细节在于操作顺序。我的做法是：先把这艘船的所有乘客全部入队完，然后再统一清理队头超时的乘客，最后输出ans。你也可以边入队边清理，但注意窗口右边界是当前船的到达时间t，左边界是t-86400，所以清理必须基于当前的t。边入边清的话，队头乘客到达时间和当前t的相对关系是不变的，也可以。统一先入后清，逻辑更清晰，不容易顾此失彼。
2.4 为什么"24小时"要用while而不是if
还有一个初学者容易忽略的点：清理超时乘客时，要用while循环，而不是if。因为可能有多个队头乘客都不满足窗口条件，得连续出队直到队头乘客在窗口内为止。
用while还有一个隐含的好处：由于每条记录的到达时间严格递增，队头只会越来越旧，一旦对某个t清理完毕，后续t变大时，之前已经被清理的乘客不可能重新进入窗口。因此，所有乘客总计只会出队一次，整体复杂度是O(总人数)，这一点是这道题能AC的复杂度根基。
3. 代码实现：C++与Python双版本
3.1 C++版完整代码与逐行注释
#include <bits/stdc++.h> using namespace std; struct Passenger { int t; // 到达时间 int c; // 国籍 }; int cnt[100005]; // 国籍计数器 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; queue<Passenger> q; int ans = 0; for (int i = 0; i < n; i++) { int t, k; cin >> t >> k; for (int j = 0; j < k; j++) { int c; cin >> c; q.push({t, c}); if (cnt[c] == 0) { ans++; // 新国籍出现 } cnt[c]++; } // 清理超过24小时的乘客 while (!q.empty() && t - q.front().t >= 86400) { int c = q.front().c; cnt[c]--; if (cnt[c] == 0) { ans--; // 该国籍消失 } q.pop(); } cout << ans << '\n'; } return 0; }注意几个点：
ios::sync_with_stdio(false);和cin.tie(nullptr);一定要加。这道题的输入量很大，不加这两行，cin读入几十万个数字会明显变慢，极端情况下可能卡超时。cnt数组开100005够吗？如果国籍编号最大是100000，那数组下标最大需要100000，开100005足够。但我不建议卡着上限开，多开一点没坏处，比如1000005，避免因为记错范围而RE。- 判断条件是
t - q.front().t >= 86400，注意是大于等于，也就是说间隔恰好86400秒的那批乘客，已经算"超过24小时"，需要出队。这个边界很重要，下面第4节会专门讲。
3.2 Python版完整代码与细节调整
import sys from collections import deque def main(): input = sys.stdin.buffer.readline n = int(input()) q = deque() cnt = [0] * 100005 ans = 0 for _ in range(n): data = list(map(int, input().split())) t, k = data[0], data[1] countries = data[2:] for c in countries: q.append((t, c)) if cnt[c] == 0: ans += 1 cnt[c] += 1 while q and t - q[0][0] >= 86400: _, c = q.popleft() cnt[c] -= 1 if cnt[c] == 0: ans -= 1 print(ans) if __name__ == "__main__": main()Python版的核心差异有三点：
- 用
sys.stdin.buffer.readline代替input()，能显著提升读入速度。数据量大的时候这个优化是实打实的。 - 因为每行的k和后面k个国籍在同一行，所以直接
list(map(int, input().split()))一次性读进来，再用data[0]、data[1]和data[2:]拆开。如果你用循环逐个数读，Python会慢很多。 - deque的
popleft()是O(1)的，但直接用列表的pop(0)是O(n)的，会超时，千万别用list冒充队列。
3.3 时间与空间复杂度分析
每个乘客入队一次、出队一次，每个人入队和出队时的cnt更新、ans更新都是O(1)操作。所以总时间复杂度是O(总乘客数)。空间上，队列最多同时存储窗口内所有乘客，最坏情况下所有乘客都在24小时窗口内，空间也是O(总乘客数)。cnt数组大小是固定的，也是O(M)，M是国籍编号最大的值。
以题目数据范围来看，总乘客数在几十万级别，这个复杂度在C++和Python里都能轻松通过。只要你没有在每次询问时去遍历窗口内的乘客，基本就达标了。
3.4 一个不太常见但更省空间的写法
如果你连存乘客的队列都想优化，可以用两个队列分别存时间和国籍，或者用数组模拟队列的head指针，每次操作只移动head。其实queue内部就是这么实现的，没必要自己造轮子。不过有一种情况可以省空间：当船上人数特别多、而滑动窗口又很短时，可以只存国籍和时间，也就是我们已有的结构。不存在进一步压缩的必要，所以老老实实存就好。
4. 常见问题与避坑实录
4.1 边界判断：恰好86400秒到底算不算
这是我被问得最多的问题，也是很多题解没有明确讲清楚的地方。题目的表述是"24小时以内到达的船"，但"以内"这个词在不同题目里有不同的定义。在这道题里，我建议你看代码中的判断条件：t - q.front().t >= 86400就出队。
什么意思？假设当前船到达时间是86400，队首乘客到达时间是0。两者相差86400秒。这个乘客算不算在当前窗口内？
按上述条件，86400 - 0 >= 86400成立，所以这个乘客要出队，也就是恰好等于24小时的乘客不算在窗口内。
如果你按>判断，也就是只有严格大于86400才出队，那么这个乘客会被保留在窗口内，答案就会有所不同，而且大概率导致WA。为什么题目是这么定义的？因为题目说的是"在过去24小时内到达"，对于时间点t，过去的24小时区间一般理解为(t-86400, t]，左开右闭。时间差正好是86400的乘客，落在左端点，不在区间内。
这个坑非常隐蔽，因为很多自己造数据的人根本测不到这种边界情况。你可以构造一个专门的测试数据去验证：
2 0 1 1 86400 1 2按题意窗口应该只有国籍2，答案输出1。你的代码要能输出这个结果，边界才算写对。
4.2 cnt数组到底开多大
国籍编号范围如果没记清，建议直接开1000005，别省这几KB。很多同学RE不是因为算法错，而是因为cnt数组下标越界。开大之后哪怕题目给的编号超过你预想的10万，也能扛住一部分。
这类计数器数组还有一个通用的优化思路：如果不确定编号上限，可以考虑用哈希表（Python的dict或C++的unordered_map）代替数组。但考虑到题目明确给出编号范围，数组是最快最稳妥的选择。哈希表的常数比数组大不少，在竞赛环境下能不用就不用。
4.3 输入卡时间：这是普及组也逃不过的宿命
P2058这道题的数据量在普及组里算大的。每行最多上百个整数，n到10万，总输入可能上百万甚至更多。用C++的cin不关同步，或者用Python的input()，都有可能拖慢程序。
我建议不管在哪个平台、用什么语言，读入优化都是基本功。C++就关同步，或者直接用scanf/printf混合（注意不要混用cin和scanf）。Python就用sys.stdin.buffer.read()一次性读入再split，或者至少用sys.stdin.buffer.readline()。实测下来，read()全部读入再逐段解析是速度最快的方案，但如果数据不大，readline也够了。
4.4 以船为单位入队的反例
前面分析过，以船为单位入队似乎可行，因为一艘船上所有乘客到达时间相同。代码可以写成这样：
struct Ship { int t; vector<int> countries; };当队首船的到达时间超出窗口时，把vector里的每个国籍cnt减掉。这本身逻辑也能跑通，但注意两点：空间上需要存所有还未出队的船的全部乘客列表，并不会比以乘客为单位省多少；时间上每次出队时要遍历一整个vector，平摊下来和逐个乘客出队是一样的。
之所以不推荐，纯粹是因为代码复杂度更高、更容易写错。比如你可能在遍历vector时忍不住去改cnt，结果忘了判断国籍数是否归零。以乘客为单位，规则只有两条，清晰不容易错。竞赛中，简单的代码才可靠。
4.5 一个容易忽略的细节：每艘船的到达时间严格递增
题目保证时间递增，这给我们一个方便：只需要用当前时间t作为右边界，队头时间一定是全局最早的，所以无需考虑"窗口内某个中间乘客的时间反而比队头更旧"这种荒谬情况。
但如果你在做类似题目时发现时间不是严格递增，那这个滑窗思路就要重新设计了。所以读题时一定要留意这个性质。
4.6 实测常见WA原因速查表
| 症状 | 可能原因 | 解决方案 |
|---|---|---|
| 答案比标准答案少1 | 边界判断用了>导致恰好86400秒的乘客未出队 | 改用>= |
| 答案比标准答案多 | 出队时忘记判断cnt[c]是否变为0，ans未减 | 出队后检查cnt[c]==0 |
| 数组越界RE | cnt数组开小了 | 开到1000005或更大 |
| 超时 | 每次询问遍历窗口内所有乘客 | 改为出入队时增量维护cnt和ans |
| Python超时 | 用input()逐行逐数读 | 改用sys.stdin.buffer.readline或read |
这张表里的前两个问题，就是我当年带人时反复看到的问题。尤其是第一个，几乎每个人都要踩一次。
5. 从这道题延伸出去的思考
"海港"这道题虽然是普及组难度，但它把好几个重要的竞赛思想串在了一起：数据结构的本质是管理变化的数据、增量维护统计信息、窗口滑动的边界处理。做透它，后续遇到类似题目也会更有底气。
我个人在实际做题中的体会是：碰到这种"按时间顺序给出事件、查询某个时间窗口内统计量"的题，第一反应就应该是滑动窗口，而不是去排序或者暴力扫。队列天然适合时间序列的先进先出，只要想清楚窗口内每个元素的最小粒度，剩下就是套模板的事情了。
另外，如果你以后遇到"窗口大小不是固定时间而是固定个数"的滑窗题，思路也是一样的：维护一个queue，超过窗口大小的队头出队，统计量增量维护。这个模板可以迁移到很多场景，比如求"任意长度不超过k的子数组中不同元素个数"之类的问题。所以别看这道题小，它其实是好几种变形题的原型。
最后再分享一个小技巧：写题解代码的时候，把输出改成用'\n'拼接最后一次性print，而不是每行print一次，在Python里能省一点时间。虽然这道题数据量下差别不大，但这个习惯在更极限的题里能救命。
做完"海港"，建议立刻去对比做几道同类型的滑窗题，比如固定窗口平均值的模板题、最长无重复子串的经典题。对比着刷几次，你会发现自己对"什么时候该用队列""什么时候该用双指针"的判断力明显提升。这就是扎实掌握一道题之后最好的回报。
