csp信奥赛C高频考点专项训练【滑动窗口】案例1最小子数组和题目描述给定一个由n个整数组成的数组和一个固定窗口长度k。窗口从数组最左边开始每次向右滑动一位直到窗口右边界到达数组末尾。请找出所有滑动窗口中窗口内元素和的最小值。输入描述第一行两个整数n和k数组长度和窗口长度满足 1 ≤ k ≤ n ≤10 6 10^6106第二行n个整数表示数组元素每个元素范围[-10000, 10000]输出描述一个整数表示所有滑动窗口中窗口内元素和的最小值样例输入7 3 1 -1 -2 -1 3 4 5样例输出-4解释窗口滑动过程窗口[1, -1, -2]和 -2窗口[-1, -2, -1]和 -4最小值窗口[-2, -1, 3]和 0窗口[-1, 3, 4]和 6窗口[3, 4, 5]和 12数据规模数组长度n最大 10^6元素绝对值最大 10^4窗口和可能达到 ±10^10需用long long解题思路问题分析需要计算所有长度为k的连续子数组的和的最小值暴力解法对每个窗口独立求和时间复杂度为 O(n*k)无法通过大数据优化思路利用滑动窗口特性通过前一个窗口和推导当前窗口和滑动窗口优化计算第一个窗口的和作为初始值窗口滑动时新窗口和 旧窗口和 新进入元素 - 离开元素时间复杂度 O(n)空间复杂度 O(1)关键细节使用long long防止求和溢出最大 |和| $10^6 $*10 4 10^4104 10^10初始最小和设为第一个窗口的和遍历时实时更新最小和代码实现#includebits/stdc.husingnamespacestd;constintN1000010;// 最大数组长度intn,k;// n: 数组长度, k: 窗口大小inta[N];// 存储数组元素下标从1开始intmain(){// 1. 数据读取cinnk;for(inti1;in;i){cina[i];}// 2. 计算第一个窗口下标 1 ~ k的和longlongwindow_sum0;for(inti1;ik;i){window_suma[i];}longlongmin_sumwindow_sum;// 初始化最小和为第一个窗口的和// 3. 滑动窗口从第 k1 个元素开始每次右移一位for(intik1;in;i){// 新窗口和 旧窗口和 新进入元素 a[i] - 离开元素 a[i-k]window_suma[i]-a[i-k];// 更新全局最小值if(window_summin_sum){min_sumwindow_sum;}}// 4. 输出结果coutmin_sum;return0;}功能分析1. 数据读取cinnk;for(inti1;in;i)cina[i];读取数组长度n和窗口大小k。将n个整数存入数组a下标从 1 开始方便后续滑动时的下标计算。2. 初始化窗口和longlongwindow_sum0;for(inti1;ik;i)window_suma[i];longlongmin_sumwindow_sum;计算第一个窗口即下标 1 到 k的元素和作为起始窗口和。同时将其作为当前最小值min_sum的初值因为至少要有一个窗口。3. 滑动更新for(intik1;in;i){window_suma[i]-a[i-k];if(window_summin_sum)min_sumwindow_sum;}循环变量i代表新进入窗口的元素的下标也是当前窗口的右边界。每次迭代从旧窗口中移除最左边的元素a[i - k]因为旧窗口的左边界是i - k。加入新元素a[i]。更新后的window_sum即为新窗口的和。与当前最小值比较若更小则替换。4. 结果输出coutmin_sum;打印所有滑动窗口中窗口和的最小值。复杂度时间O(n)仅遍历一次数组初始化 O(k) 滑动 O(n-k)。空间O(n)用于存储数组额外变量 O(1)。完整信奥赛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;}
csp信奥赛C高频考点专项训练【滑动窗口】案例1最小子数组和题目描述给定一个由n个整数组成的数组和一个固定窗口长度k。窗口从数组最左边开始每次向右滑动一位直到窗口右边界到达数组末尾。请找出所有滑动窗口中窗口内元素和的最小值。输入描述第一行两个整数n和k数组长度和窗口长度满足 1 ≤ k ≤ n ≤10 6 10^6106第二行n个整数表示数组元素每个元素范围[-10000, 10000]输出描述一个整数表示所有滑动窗口中窗口内元素和的最小值样例输入7 3 1 -1 -2 -1 3 4 5样例输出-4解释窗口滑动过程窗口[1, -1, -2]和 -2窗口[-1, -2, -1]和 -4最小值窗口[-2, -1, 3]和 0窗口[-1, 3, 4]和 6窗口[3, 4, 5]和 12数据规模数组长度n最大 10^6元素绝对值最大 10^4窗口和可能达到 ±10^10需用long long解题思路问题分析需要计算所有长度为k的连续子数组的和的最小值暴力解法对每个窗口独立求和时间复杂度为 O(n*k)无法通过大数据优化思路利用滑动窗口特性通过前一个窗口和推导当前窗口和滑动窗口优化计算第一个窗口的和作为初始值窗口滑动时新窗口和 旧窗口和 新进入元素 - 离开元素时间复杂度 O(n)空间复杂度 O(1)关键细节使用long long防止求和溢出最大 |和| $10^6 $*10 4 10^4104 10^10初始最小和设为第一个窗口的和遍历时实时更新最小和代码实现#includebits/stdc.husingnamespacestd;constintN1000010;// 最大数组长度intn,k;// n: 数组长度, k: 窗口大小inta[N];// 存储数组元素下标从1开始intmain(){// 1. 数据读取cinnk;for(inti1;in;i){cina[i];}// 2. 计算第一个窗口下标 1 ~ k的和longlongwindow_sum0;for(inti1;ik;i){window_suma[i];}longlongmin_sumwindow_sum;// 初始化最小和为第一个窗口的和// 3. 滑动窗口从第 k1 个元素开始每次右移一位for(intik1;in;i){// 新窗口和 旧窗口和 新进入元素 a[i] - 离开元素 a[i-k]window_suma[i]-a[i-k];// 更新全局最小值if(window_summin_sum){min_sumwindow_sum;}}// 4. 输出结果coutmin_sum;return0;}功能分析1. 数据读取cinnk;for(inti1;in;i)cina[i];读取数组长度n和窗口大小k。将n个整数存入数组a下标从 1 开始方便后续滑动时的下标计算。2. 初始化窗口和longlongwindow_sum0;for(inti1;ik;i)window_suma[i];longlongmin_sumwindow_sum;计算第一个窗口即下标 1 到 k的元素和作为起始窗口和。同时将其作为当前最小值min_sum的初值因为至少要有一个窗口。3. 滑动更新for(intik1;in;i){window_suma[i]-a[i-k];if(window_summin_sum)min_sumwindow_sum;}循环变量i代表新进入窗口的元素的下标也是当前窗口的右边界。每次迭代从旧窗口中移除最左边的元素a[i - k]因为旧窗口的左边界是i - k。加入新元素a[i]。更新后的window_sum即为新窗口的和。与当前最小值比较若更小则替换。4. 结果输出coutmin_sum;打印所有滑动窗口中窗口和的最小值。复杂度时间O(n)仅遍历一次数组初始化 O(k) 滑动 O(n-k)。空间O(n)用于存储数组额外变量 O(1)。完整信奥赛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;}
