They Are Everywhere（Codeforces- P701C）

年轻的宝可梦教练谢尔盖·B.发现了一栋大房子由n个公寓按从左到右的顺序排列组成。每个公寓都可以从街上进入也可以从每个公寓出去。此外每个公寓都与左边的公寓和右边的公寓相连。第1号公寓只与第2号公寓相连第n号公寓只与第n- 1号公寓相连。每个公寓里都有一种类型的宝可榜。谢尔盖·B.请求房子的居民让他按顺序进入他们的公寓来捕捉宝可榜。在与房子的居民商量后他们决定让谢尔盖·B.从街上进入一个公寓访问几个公寓然后从某个公寓出去。但他们不会让他访问同一个公寓超过一次。谢尔盖·B.非常高兴现在他想尽可能少地访问公寓以收集出现在这栋房子里的所有宝可榜。你的任务是帮助他确定他必须访问的最少公寓数量。输入第一行包含整数n(1 ≤n≤ 100 000) — 房子里的公寓数量。第二行包含长度为n的行s由英文字母的大写和小写组成第i个字母表示在第i号公寓里的宝可榜的类型。输出输出谢尔盖·B.应该访问的最少公寓数量以便捕捉到房子里出现的所有类型的宝可榜。示例 1InputcopyOutputcopy3 AaA2示例 2InputcopyOutputcopy7 bcAAcbc3示例 3InputcopyOutputcopy6 aaBCCe5注意在第一个测试中谢尔盖·B.可以从第1号公寓开始例如然后在第2号公寓结束。在第二个测试中谢尔盖·B.可以从第4号公寓开始然后在第6号公寓结束。在第三个测试中谢尔盖·B.必须从第2号公寓开始然后在第6号公寓结束。一、 题目分析【题目大意】有n个公寓排成一排每个公寓里有一只特定类型的宝可梦用大小写英文字母表示。谢尔盖希望连续访问一段公寓确保能抓到这栋楼里出现的所有种类的宝可梦并且要求访问的公寓数量最少。【核心等价转化】把题目剥开这其实是一道纯粹的字符串问题给定一个字符串s求它的一个最短的连续子串使得这个子串包含了s中出现过的所有不同的字符。【物理模型匹配】看到“连续子串”和“最短/最长”我们应该立刻想到——滑动窗口.扩张右指针向右当我们还没凑齐所有种类的宝可梦时我们只能硬着头皮继续往右走把新的公寓纳入窗口。收缩左指针向右当我们已经凑齐了所有种类时我们要考虑最左边的那间公寓是不是多余的能不能把它踢掉以缩短总长度二、 思考过程与算法设计解决这个问题我们需要分两步走第一步全图开视野明确目标我们首先需要遍历一次整个字符串用一个哈希表或 ASCII 数组统计出一共有多少种不同的宝可梦。记为cnt。这就是我们滑动窗口需要达成的“KPI”。第二步滑动窗口动态结算有了目标cnt我们就可以派出左右两个指针l和r去拉尺子了右指针r不断向右探索将路过的宝可梦种类记录下来。一旦当前窗口内的宝可梦种类数达到了cnt说明当前窗口是合法的。此时我们记录下当前窗口的长度r-l1更新最小长度mi。为了寻找更短的可能我们强制让左指针l向右收缩吐出最左边的宝可梦看看吐掉之后是不是依然合法。重复这个过程。三、 时空复杂度分析时间复杂度O(N)。在这个过程中无论是左指针还是右指针都只会一直向右走绝对不会回头。每个字符最多进入窗口一次离开窗口一次。完美线性复杂度空间复杂度O()。由于宝可梦的类型仅由大小写字母组成ASCII 码的范围在128以内。我们只需要开两个大小为 200 的整型数组来充当哈希表空间消耗微乎其微约等于 O(1)。四、 易错点总结大小写敏感题目明确说明是由大写和小写字母组成所以 A 和 a 是两种不同的宝可梦。使用数组充当哈希表时数组大小至少要开到 128推荐开 200 确保安全。无穷大初始化既然是求“最小值”记录答案的变量mi一定要初始化为一个极大的数如0x3f3f3f3f或n千万不能初始化为0。内层循环的越界右指针向右滑动的过程中务必时刻检查rs.size()防止数组越界引发错误。五、 标程注释与框架对比这里为大家提供两种实现思路。第一种直觉写法第二种是工程上的黄金模板。版本一定左探右法物理模拟的直觉呈现这套代码以左端点i为外层主循环内部用while驱动右端点探索极其生动地模拟了“拉尺子”的过程//CodeForces - 701C #include iostream #include cstring using namespace std; int n; string s;//s[i]表示在第i号公寓里的宝可榜的类型 int a[200];//记录每种类型宝可棒出现多少次 int cnt;//记录一共有多少种宝可榜 int cnt2;//记录进入的公寓内总共有多少种宝可棒 int b[200];//记录进入的公寓内每种宝可榜收集多少次 int mi0x3f3f3f3f;//记录必须访问的最小公寓数量 int main(){ cinn; cins; //记录每一种宝可榜出现多少次及总共多少种 for(int i0;is.size();i){ //如果该类型未出现过 就把类型数加一 if(a[s[i]]0) cnt; a[s[i]];//然后出现次数加一 } int r0;//从第r间公寓出去右端点实际为r1 //从第i间公寓进入实际为i1) for(int i0;is.size();i){ //向右缩小左边界 if(i0){ //当从第i间公寓进入时第i-1间收集的宝可榜就要减掉 //所以至少要从最左边1的公寓开始减即i0) //即如果左端点右移需要把前一间公寓的宝可梦吐出来 b[s[i-1]]--; //当该类型收集次数为0时 //进入的公寓内收集种类减1 if(b[s[i-1]]0) cnt2--; } //内部不断拉长右端点直到凑齐所有种类 while(rs.size()){ //如果第r间里的宝可梦尚未收集过 //就把进入公寓内宝可榜收集种类1 if(b[s[r]]0) cnt2; //然后该种宝可棒收集次数1 b[s[r]]; //如果进入的公寓内宝可棒出现总类少于所有种类就仅扩大右边界 if(cnt2cnt) r; else{//收集种类数等于总种类数 r;//边界向右移动一个备用不然下一轮会重复访问公寓 break;//退出 } } //现在可以更新一下最小进入公寓数 if(cnt2cnt) mimin(mi,r-i); } coutmi; return 0; }版本二定右缩左滑动窗口的“黄金模板”版本一的逻辑非常严密但内外循环的跳转稍显复杂。在算法竞赛中我们更推崇“外层无脑进内层看情况缩”的流水线结构这样极不容易出现越界和死循环//CodeForces - 701C #include iostream #include string #include algorithm using namespace std; int n,cnt0,current_cnt0; int total_map[200],window_map[200]; string s; int main() { ios::sync_with_stdio(false); cin.tie(0); cinns; for(char c:s) { if(total_map[c]0) cnt; total_map[c]; } int min; //答案最大就是 n int l0; //左指针 //外层永远是右指针r负责吃进新元素 for(int r0;rn;r){ //无脑吃进右边的新宝可榜 if (window_map[s[r]]0) current_cnt; window_map[s[r]]; //内层只要凑齐了就不停地尝试吐掉左边的冗余元素 while(current_cntcnt) { //满足条件更新最小值 mimin(mi,r-l1); //左指针吐出元素开始收缩 window_map[s[l]]--; if(window_map[s[l]]0) { current_cnt--; // 某种宝可榜被彻底吐光了循环将被打破 } l; } } coutmi; return 0; }