csp信奥赛C高频考点专项训练【滑动窗口】案例3小球【题目描述】有n个小球摆成一排第i个小球的颜色为c i c_ici​在这一排小球中你可以选择其中连续的K个小球并且获得他们。你喜欢五彩缤纷的颜色所以你获得的小球不同颜色越多就越高兴输出你能获得的最多的小球颜色数。【输入描述】第一行两个数字n和k表示一共有多少个小球以及你可以选择获得其中连续的K个小球。第二行n个数字表示每个小球的颜色c i c_ici​【输出描述】​ 一行一个整数表示你能获得的最多小球的颜色数量。【样例1输入】​ 5 3​ 1 2 1 3 1【样例1输出】​ 3【数据范围】​ 1≤n≤3x10 5 10^5105,1≤c i c_ici​≤1000思路分析本题要求从长度为n的序列中选取一段长度为k的连续子区间使得区间内不同颜色数值的种类数最多。如果直接枚举所有起点共n-k1个每个区间再统计颜色种数时间复杂度为O(n*k)在n最大为 3×10⁵ 时无法通过。观察发现相邻两个窗口区间之间只有两个元素发生变化左端滑出一个元素右端滑入一个元素。因此可以用滑动窗口维护当前区间内每种颜色的出现次数以及不同颜色的总数每次窗口移动时只更新这两个元素就能在O(1)时间内得到新区间的颜色种数。具体流程统计第一个窗口下标 1~k中每种颜色的出现次数并记录不同颜色数cnt。答案ans初始化为cnt。窗口从i k1开始向右滑动每次将窗口左端元素c[i-k]移出出现次数减 1如果减为 0说明该颜色在窗口内消失cnt--。将窗口右端元素c[i]移入如果该颜色之前出现次数为 0则cnt然后出现次数加 1。用当前cnt更新答案ans。遍历结束后输出ans。代码实现#includebits/stdc.husingnamespacestd;constintN3e510;// 数组最大长度intn,k;intc[N];// 存储每个小球颜色intj[N];// 颜色计数数组j[color]表示当前窗口中颜色color出现的次数intmain(){cinnk;for(inti1;in;i){cinc[i];}intcnt0;// 当前窗口中不同颜色的数量intans0;// 记录最大不同颜色数量// ---------- 初始化第一个窗口前k个小球 ----------for(inti1;ik;i){if(j[c[i]]0)// 如果该颜色之前没出现过则不同颜色数1cnt;j[c[i]];// 该颜色出现次数加1}anscnt;// 第一个窗口的结果作为初始最大值// ---------- 窗口开始向右滑动 ----------// i 表示窗口的右端下标从 k1 到 nfor(intik1;in;i){// 1. 左端元素滑出下标为 i - kintleft_colorc[i-k];j[left_color]--;// 该颜色出现次数减1if(j[left_color]0)// 若减为0则这种颜色在窗口内消失cnt--;// 2. 右端元素滑入下标为 iintright_colorc[i];if(j[right_color]0)// 若该颜色之前没出现过则不同颜色数1cnt;j[right_color];// 该颜色出现次数加1// 3. 更新答案取最大值ansmax(ans,cnt);}coutans;return0;}功能分析算法类型滑动窗口双指针 计数数组。时间复杂度O(n)因为每个元素最多被移入和移出窗口各一次每次操作都是常数时间。空间复杂度O(1)忽略输入数组计数数组大小取决于颜色值域本题c_i ≤ 1000固定为 1001 即可代码中开N3e510也完全满足。完整信奥赛C普及组CSP-J一等奖通关刷题题单及题解请关注专栏https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}