P2564 生日礼物题解基本信息项目内容题目编号、来源P2564 洛谷训练层级B 排序 滑动窗口知识版块排序、双指针、滑动窗口、哈希解题前・关键信号识别维度分析目标、约束、底层结构目标从所有彩珠中找一个最短区间包含全部 K 种颜色约束N ≤ 1e6K ≤ 60底层结构先将所有珠子按位置排序然后用双指针维护滑动窗口用 id[color] 记录每种颜色最后一次出现的位置。数据规模N ≤ 1e6O(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(f1, f1n)缺少 cmp应写sort(f1, fn1, cmp)2. 读入顺序正确但注意每种颜色的位置是升序给出的。边界和易错点1. 多个珠子可以在同一位置排序后相邻2. id 数组用 -1 初始化因为位置可以是 03. 左指针跳过条件是id[f[head].val] ! f[head].pos即当前位置不是该颜色的最新位置4. K ≤ 60id 数组开 65 即可5. N ≤ 1e6用 scanf 或 ios::sync_with_stdio(false) 加速。下次看到什么信号我应该想到这个方法看到「包含全部种类 最短区间 位置不连续」排序后滑动窗口用 id 记录每种元素最后一次出现位置。AC 完整代码#includeiostream#includealgorithm#includecstring#includequeue#includevectorusingnamespacestd;constintmaxn1000005;intid[65];inttot0;intlen0x3f3f3f3f;structnode{intpos;intval;}f[maxn];boolcmp(node a,node b){returna.posb.pos;}intmain(){memset(id,-1,sizeof(id));intn,k,t;cinnk;for(inti1;ik;i){cint;for(intj1;jt;j){tot;cinf[tot].pos;f[tot].vali;}}sort(f1,f1n,cmp);inthead1,cnt0;for(inti1;in;i){if(id[f[i].val]-1){cnt;}id[f[i].val]f[i].pos;while(headiid[f[head].val]!f[head].pos){head;}if(cntk){lenmin(len,f[i].pos-f[head].pos);}}coutlen;return0;}
