这段时间在做普及组真题的模拟练习刷到 P2058 海港这个题号时我盯着题面看了好一会儿。一艘船带着一堆乘客进港每个乘客身上挂一个来源编号然后每来一艘船都要算一算“过去24小时内所有到港船上的乘客一共出现过多少种不同的来源编号”。乍一看就是个带时间窗口的统计模拟但真动手写起来才发现没那么简单。这道题代码量不大难的点全部集中在“窗口怎么维护”上。对正在学队列、双指针和滑动窗口的人来说它是一道非常经典的上手题对准备打普及组复赛的同学来说它又是一个绕不开的常考题型。这篇文章我就把从读题到 AC 的完整思路以及调代码时踩过的几个坑拆开揉碎讲清楚。1. 先读懂题面海港到底在统计什么1.1 把题面翻译成人话题面构造了一个海港场景有 n 艘船按时间先后到达每艘船有一个到达时间 ti单位是秒还有自己的乘客名单每个乘客用一个来源编号表示。小K记录下这些信息后要求按顺序计算当第 i 艘船到达的那一刻以 ti 为“现在”向前推 24 小时也就是 86400 秒在这段时间内到达过的所有船上全部乘客的来源编号一共有多少种。注意这里统计的不是“当前这艘船上有多少种编号”而是把过去 24 小时内所有船上的乘客混在一起数一数不同编号的个数。每艘船的乘客信息在它到达之后不会消失直到超过 24 小时窗口才作废。这个“合并统计”是理解题目的关键也是最容易写错的地方。我习惯在纸上画一条时间轴来理解窗口。比如第 1 艘船在 t10 秒到达乘客来源编号是 {1,2,2,3,4}。因为此刻窗口里只有这一艘船所以结果就是 4 种对应编号 1、2、3、4。第 2 艘船在 t100 秒到达乘客是 {2,5,5}。从 100 秒往前推 86400 秒第 1 艘船还在窗口范围内所以要把两艘船的数据合并一共有编号 1、2、3、4、5答案是 5。如果第 3 艘船到了 t90000 秒乘客是 {6}那就要注意了90000 减去 86400 等于 3600而第 1、2 艘船的到达时间是 10 和 100都小于 3600说明它们已经不在“过去 24 小时”里了。窗口里只剩下第 3 艘船答案是 1。这个例子基本就说清楚了题目的语义也直接引出了核心问题随着新船不断到来旧船陆续过期窗口里的内容一直在动态变化。1.2 数据范围为什么逼着你想新办法普及组这道题给的数据范围是 n 不超过 100000所有船上的乘客总数 sum(k) 不超过 300000。如果采用最笨的办法每来一艘船就把当前窗口内所有船的乘客重新扫一遍算一遍种类数那复杂度大约在 n 乘以 sum(k) 的量级最坏能到 10 亿次以上的操作在竞赛时间限制下基本不可能通过。这实际上是题目在提示你不要重复统计。观察可以发现船的到达时间是严格递增的这意味着“过去 24 小时窗口”的左边界也只能单调向右移动不会回退。这个性质恰好是双指针和滑动窗口能够成立的根基。每个乘客只需要被加入一次、被移除一次总复杂度就能降到 O(sum(k)n)。这也是这道题隐藏在模拟外壳下的真正考点能不能想到用增量维护来替代重复扫描。2. 滑动窗口思路从“重新数”到“增量维护”2.1 窗口的本质是不断右移的区间把时间轴横过来看每艘船就是轴上的一个点挂着它的乘客名单。当前船 right 到达时窗口就是 [t[right]-86400ε, t[right]] 这个左闭右开区间内的所有船。因为时间右端点一直在变大窗口左端点也只能不断向右推绝对不会出现左端点往回走的可能。这正是滑动窗口适用的典型场景。具体维护时需要准备三样东西一个指针 left指向窗口内最早到达且还没过期的船编号。一个计数数组 cnt[x]记录来源编号 x 在当前窗口内出现的总人数。一个整数 ans记录当前窗口内不同来源编号的种类数。核心操作只有两步新船 right 到达时把它整艘船的乘客加入统计所有与当前船时间差已经达到 86400 秒的旧船按编号顺序整艘移出统计。每处理完一艘新船ans 就是当前答案。用计数数组而不是 set 或 bool 数组是有原因的。因为同一个来源编号可能在同一艘船或不同船上出现多次如果只记录“出现过没有”移除旧船时很容易误删掉仍然存在的编号。只有记录具体的出现次数才能在某个编号的计数从 1 变 0 时确认这个种类真的从窗口里消失了。2.2 两种实现方案按船滑动还是按乘客入队第一种方案是直接把每一艘船看成一个整体元素用双指针在船的编号上滑动。每艘船保存自己的乘客列表left 和 right 都是船的编号。这种做法的好处是贴合题目原始数据结构不需要把同一艘船的乘客拆散逻辑非常清楚。第二种方案是以单个乘客为队列元素每个元素记录两样信息这艘船到达的时间 ti以及这名乘客的来源编号 x。新船到达时把它的 k 名乘客逐一入队统计前从队首开始弹出所有满足“队首时间 当前时间 - 86400”的乘客每弹出一名乘客就把对应的 cnt[x] 减掉。这种方式更贴近队列的原生语义但代码上手时容易忽略一个细节同一艘船的多名乘客是连续入队的弹出时也会连续出现在队首所以逻辑上不会出现一艘船的乘客被拆碎弹出的情况。我推荐第一种方案因为这道题本身就是按船给出数据的用船的编号做双指针代码更短也不容易把自己绕晕。后面给出的参考代码就是基于这个方案。2.3 先移除过期船还是先加入新船到底有没有区别我见过不少同学在这两个操作的顺序上纠结。先说结论对于最终答案先移后加和先加后移结果是一样的因为新船是当前时刻到达的船它的到达时间不可能小于自己的时间戳所以在任何情况下它都不应该被当作过期船移出。区别主要在于调试时的心智负担。我个人的建议是统一采用“先移除过期船再加入当前新船”的流程。这样在做移除操作时cnt 数组里存储的数据就是窗口内 [left, right-1] 这些旧船的状态语义清晰不容易在调试时把新加入的数据误扣掉。尤其是刚开始学滑动窗口的阶段用一个固定的操作顺序能省下大量 debug 时间。3. 核心代码实现与逐段解析3.1 完整参考代码下面是按“船的编号双指针”方案写的参考代码使用 C已经加上关键注释。#include bits/stdc.h using namespace std; const int MAXN 100005; // 来源编号上限 int cnt[MAXN]; // cnt[x]来源编号 x 在当前窗口内出现的人数 vectorint pass[MAXN]; // pass[i]第 i 艘船上的乘客来源编号列表 long long tim[MAXN]; // tim[i]第 i 艘船的到达时间用 long long 更稳妥 int main() { int n; scanf(%d, n); int ans 0; // 当前窗口内不同来源编号的种类数 int left 1; // 窗口左端对应的船编号 for (int right 1; right n; right) { int k; scanf(%lld%d, tim[right], k); for (int j 0; j k; j) { int x; scanf(%d, x); pass[right].push_back(x); } // 第一步把与当前船时间差已达到 86400 秒的旧船整体移出窗口 while (left right tim[right] - tim[left] 86400) { for (int j 0; j (int)pass[left].size(); j) { int x pass[left][j]; cnt[x]--; if (cnt[x] 0) ans--; } left; } // 第二步把当前新船的乘客全部加入窗口 for (int j 0; j (int)pass[right].size(); j) { int x pass[right][j]; if (cnt[x] 0) ans; cnt[x]; } printf(%d\n, ans); } return 0; }这段代码可以直接提交但在自己的环境里跑的时候要留意数据范围如果题库给出的来源编号上限不是 100000需要相应调整 MAXN。如果编号范围更大可以考虑用 map 或 unordered_map 代替静态数组但比赛环境下静态数组访问更快。3.2 关键代码逐行讲解先看移除部分。while 循环的判断条件是 tim[right] - tim[left] 86400意思是只要 left 这艘船到达时间已经比当前船的到达时间早至少 86400 秒它就不属于“过去 24 小时”了必须整艘移出。移出的具体做法是遍历该船乘客列表把每个人的 cnt[x] 减 1同时如果某个编号的计数从 1 变成 0就说明这个种类从窗口里彻底消失了ans 需要减 1。这里最需要注意的是 ans 的更新时机。ans 代表的不是人数而是“编号的种类数”。cnt[x] 变成 2、变成 3ans 都不动只有当 cnt[x] 从 0 变成 1说明出现了一个窗口里之前没有的新编号ans 才加 1反过来只有当 cnt[x] 从 1 变成 0说明这个编号在窗口里已经一个人都没有了ans 才减 1。这个规则是整个代码能够正确运行的基石。加入部分的逻辑完全对称。遍历新船乘客列表如果 cnt[x] 是 0先把 ans 加 1再执行 cnt[x]。注意一定要先判断再加顺序反了会把“已经是 0”和“从 0 变 1”的判别条件破坏掉导致答案错误。3.3 复杂度和内存评估每个乘客只会被加入一次、移出一次每个船编号最多被 left 指针经过一次所以整体时间复杂度是 O(n sum(k))也就是船数加乘客总数。这个复杂度在 100000 艘船、300000 名乘客的数据规模下非常轻松运行时间基本可以忽略不计。内存方面cnt 数组和 tim 数组都是 O(100000) 量级所有 vector 的总体积取决于乘客总数最多约 300000 个 int。没有什么内存压力。唯一要提醒的是不要开一个 n 行 k 列的二维数组去存全部乘客那会直接内存溢出用 vector 按需存储才是正确姿势。4. 易错点与实战排查4.1 边界条件24小时含不含整点怎么判断这是海港这道题里最有争议的细节。两艘船的到达时间差如果刚好是 86400 秒那艘更早的船还算不算“24 小时以内”我的处理是用 触发移除也就是说只保留时间差严格小于 86400 秒的船。实际上这个写法能在 NOIP 官方数据下通过我按照这个条件写的代码 AC 过。但不同题库、不同翻译版本的题面可能对边界定义有细微差别。最稳妥的办法是先用样例手算一遍看样例结果对应的是“含整点”还是“不含整点”再决定把 while 条件写成 还是 。很多新手在这一个判断上耗很久其实没必要模拟题里这种边界影响的对象往往只有极少数的船先把主体逻辑写对再拿极端数据测一下就能确定。4.2 移除旧船时别把刚加入的新船也误扣掉如果你习惯先加新船再移旧船一定要时刻提醒自己left 最多只能移动到 right 当前这一艘不能再往前。因为当 left 和 right 相等时时间差是 0必然小于 86400循环会自然终止。但如果代码里没有控制 left 的移动范围或者把两个操作顺序写反很容易在调试时看到 ans 莫名其妙变成负数。为了减少这种风险我强烈建议固定用“先移除后加入”的顺序。这样在移除阶段cnt 数组里装的完全是旧船的数据不会混入新船的信息逻辑上更干净出问题时也更容易通过打印 cnt 数组来定位。4.3 ans 的加加减减必须绑定 0/1 转换我见过不少初学者写出这样的代码加入乘客时无条件 ans移除乘客时无条件 ans--。结果就是同一个来源编号出现在两艘不同船上时ans 会被反复加两次减一次答案完全错乱。这是对“种类数”和“人数”两个概念没有区分清楚导致的。记住这条铁律cnt[x] 记录的是“人数”ans 记录的是“种类数”。人数变多不代表种类一定变多人数减少也不代表种类一定减少。只有当 cnt[x] 从 0 变成 1或者从 1 变成 0ans 才需要更新。每次对 cnt[x] 的修改前后都要检查这两个特殊状态。4.4 读写速度和存储方式的小细节n 是 100000乘客总数是 300000用 scanf、printf 和用关闭同步后的 cin、cout 差距不大但竞赛里我一般习惯用 scanf、printf减少底层同步可能带来的性能抖动。如果坚持用 cin、cout记得在 main 开头加 ios::sync_with_stdio(false); 和 cin.tie(nullptr);。另外要注意pass 数组如果你开成静态二维数组比如 int pass[100005][100005]在栈里根本无法分配程序会直接崩溃。用 vector 动态扩容是正确方式它的总容量只跟实际乘客数挂钩不会浪费空间。4.5 一个完整的手算过程帮你核对思路我构造一个小样例n4四艘船的信息如下船1t1乘客 {10, 20}船2t100乘客 {10}船3t86500乘客 {30, 40}船4t86501乘客 {20}人工推一遍整个流程当前船到达时间主要操作leftans输出船11无过期船加入10和20122船2100距船1只有99秒没过期加入10122船386500船1距当前86499秒过期移出船2距当前86400秒正好达到阈值也移出加入30和40322船486501距船3只有1秒无船过期加入20333这里船2和船3的时间差正好是 86400 秒我们的代码用 判定所以船2会被移出窗口。如果这个样例的预期输出不同就要立刻回头检查边界条件是不是理解反了。这道题的样例数据其实很容易覆盖到这种“恰好 24 小时”的场景动手算一遍比嘴上纠结要靠谱得多。5. 从海港延伸开去这个模型还能用在哪些地方5.1 滑动窗口维护动态集合的通用套路海港这道题表面上是“船和乘客”抽象之后其实是一个很通用的模型按照时间顺序不断有对象到达每个对象携带若干标签每次查询要求统计“以当前时刻为右端点向前固定时间长度”的时间窗口内一共出现过多少种不同的标签。这个模型在真实工作里也非常常见。比如统计一个直播间最近 30 分钟的弹幕中有多少位不同用户发言或者统计一个服务最近 1 小时的请求来自多少个不同的调用方底层思路都是一模一样的维护一个按时间排序的队列动态增删元素再用计数数组和答案变量做增量维护。把海港这道题吃透这些场景的代码你几乎可以直接套。5.2 类似题目怎么迁移思路如果窗口的长度不是 86400 秒而是固定的 k 个元素比如“连续 k 个位置中有多少种不同的数字”算法框架完全一样只需要把按时间移除改为按元素个数移除。如果题目要求的是统计窗口内出现次数最多的标签那计数数组就不够用了需要额外配合优先队列或者平衡树来维护频次排行榜。但海港这道题只要求“种类数”计数数组加一个 ans 变量就是最性价比的方案。还有一种变形是查询点不是“每艘船到达时”而是任意时间点。那就不能只按船的下标滑动了通常需要离线处理所有查询按时间排序统一推进窗口或者使用可删除的线段树、树状数组来维护动态集合。那些题目难度会更高一层但核心思想仍然是增量维护。5.3 做模拟题的一点方法论海港属于“表面模拟、实际考数据结构思维”的典型题。读题之后先别急着写代码花两分钟画一条时间轴把三艘、四艘船的窗口变化写出来确认自己理解的和题意完全一致再动手敲键盘。这个小习惯可以帮助你避开大量因为题意误读导致的差错了。我每次做带窗口概念的题目都会在草稿纸上先把样例的窗口“可视化”一遍这对理解边界条件特别有帮助。至于代码实现我的建议是先用双指针按船滑动跑通小样例之后再用极端数据测试所有船同一秒到达、所有乘客来源编号完全相同、两艘船时间差恰好等于 86400。这些测试全过了基本就可以安心提交了。等你对解法足够熟悉再去尝试用“每名乘客入队”的版本你会发现两种写法的本质完全一致只是习惯偏好不同罢了。
