P2564 生日礼物题解
基本信息
| 项目 | 内容 |
|---|
| 题目编号、来源 | P2564 洛谷 |
| 训练层级 | B 排序 + 滑动窗口 |
| 知识版块 | 排序、双指针、滑动窗口、哈希 |
解题前・关键信号识别
| 维度 | 分析 |
|---|
| 目标、约束、底层结构 | 目标：从所有彩珠中找一个最短区间，包含全部 K 种颜色；约束：N ≤ 1e6，K ≤ 60；底层结构：先将所有珠子按位置排序，然后用双指针维护滑动窗口，用 id[color] 记录每种颜色最后一次出现的位置。 |
| 数据规模 | N ≤ 1e6，O(N log N) 排序 + O(N) 滑动窗口，可通过。 |
| 候选算法和依据 | 排序 + 滑动窗口；依据：需要找包含所有种类的最短区间，P1638 逛画展的升级版（位置不连续，需要先排序）。 |
| 复杂度预判 | 排序 O(N log N)，滑动窗口 O(N)，总 O(N log N)；空间 O(N)。 |
解题后・外化复盘
| 维度 | 内容 |
|---|
| 实现结构 / 核心思路 | 第一步将每种颜色的所有位置读入结构体数组 (pos, color)，按 pos 升序排序；第二步用滑动窗口 [head, i] 维护当前区间，id[color] 记录该颜色最后一次出现的位置；第三步右指针 i 不断右移，更新 id；第四步左指针 head 跳过所有“不是该颜色最后一次出现”的旧位置；第五步当 cnt == K（所有颜色都出现过）时，用当前右端点位置减去左端点位置更新答案。 |
| 错因回溯 | 1. 排序函数写错：sort(f+1, f+1+n)缺少 cmp，应写sort(f+1, f+n+1, cmp)；2. 读入顺序正确但注意每种颜色的位置是升序给出的。 |
| 边界和易错点 | 1. 多个珠子可以在同一位置，排序后相邻；2. id 数组用 -1 初始化，因为位置可以是 0；3. 左指针跳过条件是id[f[head].val] != f[head].pos，即当前位置不是该颜色的最新位置；4. K ≤ 60，id 数组开 65 即可；5. N ≤ 1e6，用 scanf 或 ios::sync_with_stdio(false) 加速。 |
| 下次看到什么信号，我应该想到这个方法 | 看到「包含全部种类 + 最短区间 + 位置不连续」，排序后滑动窗口，用 id 记录每种元素最后一次出现位置。 |
AC 完整代码
#include<iostream>#include<algorithm>#include<cstring>#include<queue>#include<vector>usingnamespacestd;constintmaxn=1000005;intid[65];inttot=0;intlen=0x3f3f3f3f;structnode{intpos;intval;}f[maxn];boolcmp(node a,node b){returna.pos<b.pos;}intmain(){memset(id,-1,sizeof(id));intn,k,t;cin>>n>>k;for(inti=1;i<=k;i++){cin>>t;for(intj=1;j<=t;j++){tot++;cin>>f[tot].pos;f[tot].val=i;}}sort(f+1,f+1+n,cmp);inthead=1,cnt=0;for(inti=1;i<=n;i++){if(id[f[i].val]==-1){cnt++;}id[f[i].val]=f[i].pos;while(head<=i&&id[f[head].val]!=f[head].pos){head++;}if(cnt==k){len=min(len,f[i].pos-f[head].pos);}}cout<<len;return0;}
