news 2026/6/10 16:52:09

csp信奥赛C++标准模板库STL案例应用17

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
csp信奥赛C++标准模板库STL案例应用17

csp信奥赛C++标准模板库STL案例应用17

deque实践

题目描述

一个含有n nn项的数列，求出每一项前的m mm个数到它这个区间内的最小值。若前面的数不足m mm项则从第1 11个数开始，若前面没有数则输出0 00。

输入格式

第一行两个整数，分别表示n nn，m mm。

第二行，n nn个正整数，为所给定的数列a i a_iai​。

输出格式

n nn行，每行一个整数，第i ii个数为序列中a i a_iai​之前m mm个数的最小值。

输入输出样例 1
输入 1
6 2 7 8 1 4 3 2
输出 1
0 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×106，1 ≤ a i ≤ 3 × 10 7 1\le a_i\le3\times10^71≤ai​≤3×107。

思路分析

本题要求对每个位置i，找到区间[i-m, i-1]的最小值（如果区间不足m个元素，则从第一个元素开始）。这是一个典型的滑动窗口最小值问题。

核心算法：单调队列

使用一个双端队列维护一个递增的单调队列：

  1. 队列中存储数组元素的索引，这些索引对应的值保持单调递增
  2. 对于每个新元素，从队尾移除比它大的元素（保证队列单调性）
  3. 从队首移除超出窗口范围的元素
  4. 队首元素就是当前窗口的最小值
算法复杂度
  • 时间复杂度：O(n)，每个元素最多入队和出队一次
  • 空间复杂度：O(m)，队列中最多存储m个索引

代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,m;cin>>n>>m;// 读取n和mvector<int>a(n+1);// 1-indexed数组，方便处理// 读取数组for(inti=1;i<=n;i++){cin>>a[i];}deque<int>dq;// 存储索引的单调队列（双端队列）// 第一个元素前面没有元素，输出0cout<<0<<'\n';// 处理从第1个到第n-1个元素（为后续元素提供窗口最小值）for(inti=1;i<n;i++){// 维护队列单调性：从队尾移除比当前元素大的元素// 因为当前元素比它们小且位置更靠后，所以这些元素不可能成为未来窗口的最小值while(!dq.empty()&&a[dq.back()]>=a[i]){dq.pop_back();}// 将当前元素索引加入队列dq.push_back(i);// 移除超出窗口范围的元素// 窗口范围是 [i-m+1, i]（对于下一轮i+1来说，需要的是[i-m+2, i+1]）// 但我们要为第i+1个元素找前m个元素的最小值，所以这里检查是否超出[i-m+1, i]while(!dq.empty()&&dq.front()<=i-m){dq.pop_front();}// 输出当前窗口的最小值（即为第i+1个元素前m个元素的最小值）// 如果队列为空，说明前面没有元素，输出0if(dq.empty()){cout<<0<<'\n';}else{cout<<a[dq.front()]<<'\n';}}return0;}

功能分析

输入处理
  • 第一行：读取n（数列长度）和m（窗口大小）
  • 第二行：读取n个正整数到数组a[1…n]（使用1-indexed方便理解）
特殊处理
  • 对于第一个元素（i=1）：前面没有元素，直接输出0
滑动窗口处理
  • 队列初始化：开始时队列为空
  • 单调性维护：
    • 当新元素加入时，从队尾移除所有值大于等于它的元素
    • 这样保证队列中的元素值严格递增
  • 窗口范围维护：
    • 移除队首超出当前窗口范围的元素（索引小于等于i-m）
  • 输出结果：
    • 队首元素即为当前窗口的最小值
    • 如果队列为空，输出0

示例演示（输入样例）

输入：

6 2 7 8 1 4 3 2

处理过程：

i=1: 输出0（第一个元素前无元素） i=1: 处理元素a[1]=7，队列为空→队列变为[1]，为a[2]准备窗口 窗口[1]，最小值a[1]=7，输出7 i=2: 处理元素a[2]=8，队尾a[1]=7<8→队列变为[1,2] 窗口[1,2]，最小值a[1]=7，输出7 i=3: 处理元素a[3]=1，队尾a[2]=8>=1→弹出2，队尾a[1]=7>=1→弹出1 队列变为[3] 窗口[2,3]，最小值a[3]=1，输出1 i=4: 处理元素a[4]=4，队尾a[3]=1<4→队列变为[3,4] 窗口[3,4]，最小值a[3]=1，输出1 i=5: 处理元素a[5]=3，队尾a[4]=4>=3→弹出4，队尾a[3]=1<3→队列变为[3,5] 窗口[4,5]，最小值a[3]=1，但索引3超出窗口[4,5]（3<=5-2=3）→弹出3 队列变为[5]，最小值a[5]=3，输出3

输出：

0 7 7 1 1 3

注意事项

  1. 使用deque而不是普通队列，因为需要从两端操作
  2. 队列中存储索引而不是值，方便判断是否超出窗口范围
  3. 注意边界条件：当i=1时直接输出0，后续处理从i=1开始
  4. 时间复杂度必须为O(n)，不能使用O(nm)的暴力解法

完整系列资料，请查看专栏：《csp信奥赛C++标准模板库STL》
https://blog.csdn.net/weixin_66461496/category_13108077.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;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 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/6/10 12:59:51

超详细版UVC驱动移植教程：适配不同ARM平台实践

手把手教你搞定UVC驱动移植&#xff1a;从零适配全志、瑞芯微到i.MX系列ARM平台你有没有遇到过这种情况——手头一个标准的USB摄像头&#xff0c;插到开发板上却“毫无反应”&#xff1f;dmesg翻遍了也没见个影子&#xff0c;/dev/video0更是无从谈起。明明在PC上即插即用&…

作者头像 李华
网站建设 2026/6/10 13:00:10

QQ音乐解析工具终极指南：2025年免费获取高品质音乐资源

QQ音乐解析工具终极指南&#xff1a;2025年免费获取高品质音乐资源 【免费下载链接】MCQTSS_QQMusic QQ音乐解析 项目地址: https://gitcode.com/gh_mirrors/mc/MCQTSS_QQMusic 还在为无法下载QQ音乐的付费歌曲而烦恼吗&#xff1f;QQ音乐解析工具为您提供完美的解决方案…

作者头像 李华
网站建设 2026/6/10 12:59:20

Windows安卓应用安装终极指南：告别模拟器，体验原生安装

Windows安卓应用安装终极指南&#xff1a;告别模拟器&#xff0c;体验原生安装 【免费下载链接】APK-Installer An Android Application Installer for Windows 项目地址: https://gitcode.com/GitHub_Trending/ap/APK-Installer 还在为复杂的安卓模拟器设置而烦恼吗&am…

作者头像 李华
网站建设 2026/6/10 14:41:33

如何快速掌握SDR++：新手必学的10个核心技巧

还在为复杂的软件定义无线电工具而烦恼吗&#xff1f;SDR作为一款跨平台的开源SDR软件&#xff0c;以其轻量级设计和直观界面赢得了众多无线电爱好者的青睐。无论你是想收听本地广播电台&#xff0c;还是探索神秘的卫星信号&#xff0c;这款专业的软件定义无线电工具都能为你提…

作者头像 李华
网站建设 2026/6/10 12:52:46

es安装系统学习：覆盖集群与节点设置

从零构建高可用Elasticsearch集群&#xff1a;一次讲透节点角色与集群配置你是不是也经历过这样的场景&#xff1f;刚在服务器上跑起一个单机版的 Elasticsearch&#xff0c;索引几万条日志还挺快。结果一上线生产&#xff0c;数据量暴涨、查询变慢、节点频繁失联……最后发现不…

作者头像 李华
网站建设 2026/6/10 12:59:52

东南大学论文排版3分钟实战手册：告别格式烦恼的实用指南

东南大学论文排版3分钟实战手册&#xff1a;告别格式烦恼的实用指南 【免费下载链接】SEUThesis 项目地址: https://gitcode.com/gh_mirrors/seu/SEUThesis 还在为毕业论文格式烦恼吗&#xff1f;东南大学论文模板库就是你的救星&#xff01;这个专为东大学子量身打造的…

作者头像 李华