P8661日志统计题解复盘

P8647 [蓝桥杯 2018 省 A] 日志统计 题解复盘基本信息项目内容题目编号、来源P8647 洛谷 / 蓝桥杯 2018 年省赛 A/B/C 组训练层级B变式题 双指针 / 滑动窗口 排序知识版块滑动窗口、双指针、排序、哈希表/桶排序解题前・关键信号识别维度分析目标、约束、底层结构目标找出所有“热帖”——任意长度为 D 的时间窗口内收到 ≥ K 个赞的帖子约束N ≤ 1e5ts,id ≤ 1e5底层结构按帖子分组每组按时间排序用滑动窗口双指针检查是否存在长度 D 的窗口内有 ≥ K 个赞。数据规模N ≤ 1e5O(N log N) 排序 O(N) 滑动窗口可通过暴力 O(N²) 会超时。候选算法和依据滑动窗口 / 双指针依据每个帖子单独处理时间排序后用双指针 l, r 维护窗口当 ts[r] - ts[l] D 时窗口合法若窗口内赞数 ≥ K 则标记热帖。复杂度预判排序 O(N log N)滑动窗口 O(N)总 O(N log N)空间 O(N)。解题后・外化复盘从会一次到稳定会维度内容实现结构 / 核心思路第一步读入所有 (ts, id)存入 vector 并按 id 分组第二步对每个 id 的点赞时间列表排序第三步对每个 id 的时间列表使用滑动窗口r 不断右移当 ts[r] - ts[l] D 时 l 右移缩窗口若窗口内点数 ≥ K 则该 id 是热帖第四步按 id 升序输出所有热帖。核心思想同一帖子点赞时间排序后若窗口左端和右端时间差 D则窗口内所有点赞都在一个合法时间段内。错因回溯逻辑BUG / 代码实现BUG1. 忘记按 id 分组直接全局滑窗口窗口内可能有多个帖子混在一起2. 判断条件写反用 D缩窗口不是 D3. 重复输出同一个 id没有用 bool 数组标记已输出4. id 和 ts 范围包括 0数组/vector 要能处理 0 下标。边界和易错点1. 一个 id 的点赞次数可能不足 K直接跳过2. D 是半开区间 [T, TD)所以 ts[r] - ts[l] D 时窗口合法一旦 D 就缩左端3. 点赞数量刚好 K 时也算热帖4. 输出按 id 升序不是按时间5. 多个相同 id 的点赞时间可能重复同一时刻多次点赞仍算多条正常累加即可6. 用times[i].size() k提前剪枝优化效率。下次看到什么信号我应该想到这个方法看到「固定长度区间/时间段 计数 ≥ K 多组独立数据」按组排序 滑动窗口。AC 完整代码#includeiostream#includealgorithm#includeset#includequeue#includevectorusingnamespacestd;intn,d,k;constintmaxn1e56;vectorinttimes[maxn];boolvis[maxn];intmain(){cinndk;for(inti0;in;i){intts,id;cintsid;times[id].push_back(ts);}for(inti0;imaxn;i){if((int)times[i].size()k)continue;sort(times[i].begin(),times[i].end());intl0;for(intr0;r(int)times[i].size();r){while(times[i][r]-times[i][l]d){l;}if(r-l1k){vis[i]1;break;}}}for(inti0;imaxn;i){if(vis[i]){coutiendl;}}return0;}