企业官网建设流程全解析

织梦网站栏目管理空白,柳州建设网经济适用房,免费做店招哪个网站好,手游折扣平台最新排名csp信奥赛C标准模板库STL案例应用17 deque实践 题目描述 一个含有 nnn 项的数列#xff0c;求出每一项前的 mmm 个数到它这个区间内的最小值。若前面的数不足 mmm 项则从第 111 个数开始#xff0c;若前面没有数则输出 000。 输入格式 第一行两个整数#xff0c;分别表示…csp信奥赛C标准模板库STL案例应用17deque实践题目描述一个含有n nn项的数列求出每一项前的m mm个数到它这个区间内的最小值。若前面的数不足m mm项则从第1 11个数开始若前面没有数则输出0 00。输入格式第一行两个整数分别表示n nnm mm。第二行n nn个正整数为所给定的数列a i a_iai​。输出格式n nn行每行一个整数第i ii个数为序列中a i a_iai​之前m mm个数的最小值。输入输出样例 1输入 16 2 7 8 1 4 3 2输出 10 7 7 1 1 3说明/提示对于100 % 100\%100%的数据保证1 ≤ m ≤ n ≤ 2 × 10 6 1\le m\le n\le2\times10^61≤m≤n≤2×1061 ≤ a i ≤ 3 × 10 7 1\le a_i\le3\times10^71≤ai​≤3×107。思路分析本题要求对每个位置i找到区间[i-m, i-1]的最小值如果区间不足m个元素则从第一个元素开始。这是一个典型的滑动窗口最小值问题。核心算法单调队列使用一个双端队列维护一个递增的单调队列队列中存储数组元素的索引这些索引对应的值保持单调递增对于每个新元素从队尾移除比它大的元素保证队列单调性从队首移除超出窗口范围的元素队首元素就是当前窗口的最小值算法复杂度时间复杂度O(n)每个元素最多入队和出队一次空间复杂度O(m)队列中最多存储m个索引代码实现#includebits/stdc.husingnamespacestd;intmain(){intn,m;cinnm;// 读取n和mvectorinta(n1);// 1-indexed数组方便处理// 读取数组for(inti1;in;i){cina[i];}dequeintdq;// 存储索引的单调队列双端队列// 第一个元素前面没有元素输出0cout0\n;// 处理从第1个到第n-1个元素为后续元素提供窗口最小值for(inti1;in;i){// 维护队列单调性从队尾移除比当前元素大的元素// 因为当前元素比它们小且位置更靠后所以这些元素不可能成为未来窗口的最小值while(!dq.empty()a[dq.back()]a[i]){dq.pop_back();}// 将当前元素索引加入队列dq.push_back(i);// 移除超出窗口范围的元素// 窗口范围是 [i-m1, i]对于下一轮i1来说需要的是[i-m2, i1]// 但我们要为第i1个元素找前m个元素的最小值所以这里检查是否超出[i-m1, i]while(!dq.empty()dq.front()i-m){dq.pop_front();}// 输出当前窗口的最小值即为第i1个元素前m个元素的最小值// 如果队列为空说明前面没有元素输出0if(dq.empty()){cout0\n;}else{couta[dq.front()]\n;}}return0;}功能分析输入处理第一行读取n数列长度和m窗口大小第二行读取n个正整数到数组a[1…n]使用1-indexed方便理解特殊处理对于第一个元素i1前面没有元素直接输出0滑动窗口处理队列初始化开始时队列为空单调性维护当新元素加入时从队尾移除所有值大于等于它的元素这样保证队列中的元素值严格递增窗口范围维护移除队首超出当前窗口范围的元素索引小于等于i-m输出结果队首元素即为当前窗口的最小值如果队列为空输出0示例演示输入样例输入6 2 7 8 1 4 3 2处理过程i1: 输出0第一个元素前无元素 i1: 处理元素a[1]7队列为空→队列变为[1]为a[2]准备窗口 窗口[1]最小值a[1]7输出7 i2: 处理元素a[2]8队尾a[1]78→队列变为[1,2] 窗口[1,2]最小值a[1]7输出7 i3: 处理元素a[3]1队尾a[2]81→弹出2队尾a[1]71→弹出1 队列变为[3] 窗口[2,3]最小值a[3]1输出1 i4: 处理元素a[4]4队尾a[3]14→队列变为[3,4] 窗口[3,4]最小值a[3]1输出1 i5: 处理元素a[5]3队尾a[4]43→弹出4队尾a[3]13→队列变为[3,5] 窗口[4,5]最小值a[3]1但索引3超出窗口[4,5]35-23→弹出3 队列变为[5]最小值a[5]3输出3输出0 7 7 1 1 3注意事项使用deque而不是普通队列因为需要从两端操作队列中存储索引而不是值方便判断是否超出窗口范围注意边界条件当i1时直接输出0后续处理从i1开始时间复杂度必须为O(n)不能使用O(nm)的暴力解法完整系列资料请查看专栏《csp信奥赛C标准模板库STL》https://blog.csdn.net/weixin_66461496/category_13108077.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}一、CSP信奥赛C通关学习视频课C语法基础C语法进阶C算法C数据结构CSP信奥赛数学CSP信奥赛STL二、CSP信奥赛C竞赛拿奖视频课信奥赛csp-j初赛高频考点解析CSP信奥赛C复赛集训课12大高频考点专题集训三、考级、竞赛刷题题单及题解GESP C考级真题题解CSP信奥赛C初赛及复赛高频考点真题解析CSP信奥赛C一等奖通关刷题题单及题解详细内容1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转2025 csp-j 复赛真题及答案解析最新更新2025 csp-x(山东) 复赛真题及答案解析最新更新2025 csp-x(河南) 复赛真题及答案解析最新更新2025 csp-x(辽宁) 复赛真题及答案解析最新更新2025 csp-x(江西) 复赛真题及答案解析最新更新2025 csp-x(广西) 复赛真题及答案解析最新更新2020 ~ 2024 csp 复赛真题题单及题解2019 ~ 2022 csp-j 初赛高频考点真题分类解析2021 ~ 2024 csp-s 初赛高频考点解析2023 ~ 2024 csp-x (山东)初赛真题及答案解析2024 csp-j 初赛真题及答案解析2025 csp-j 初赛真题及答案解析最新更新2025 csp-s 初赛真题及答案解析最新更新2025 csp-x (山东)初赛真题及答案解析(最新更新)2025 csp-x (江西)初赛真题及答案解析(最新更新)2025 csp-x (辽宁)初赛真题及答案解析(最新更新)CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转129 道刷题练习和详细题解涉及模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图4、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}