当前位置: 首页 > news >正文

E-魔法猫咪(遇到过的题,做个笔记)

题解:

来自学长们思路:

其中一种正解是写单调队列。限制队列内的数单调递增,方法为每当新来的数据比当前队尾数据小时队 尾出列,直到能够插入当前值,这保证了队头永远是最小值。因此总体思路是队尾不断插入新值的同时 不断输出当前队头元素。在输出队头元素时有两点要注意:

1. 队尾前进 m次后再开始输出。

2. 确认当前队头值的下标仍在区间范围内,反之则需要队头出队直到进入当前区间。

#include <iostream>
#include <vector>
using namespace std;
int main()
{int n, m;cin >> n >> m;vector<int>arr(n + 1);			//用于存放数据vector<int>q(n + 1);		//存最小数的下标int head = 1, tail = 0;			//模拟双向队列,把头定为 q[1],尾先定为q[0],且该队列是单调递增的for (int i = 1; i <= n; i++){cin >> arr[i];while (1)	//通过移动末尾的位置来弹出队尾元素,直到队尾能插入新的更小的数据{if (arr[i] < arr[q[tail]] && head <= tail)	tail--;	//尾移动弹出元素过程中,要保证更小的元素能作为队头所以才是(&&head<=tail)else{q[++tail] = i;		//将元素插入队尾break;		//更小数据插入后就结束循环}}if (i - q[head] + 1 > m)	head++;		//发现该元素与队头元素的距离超过了m,就让队头的位置往后移动,因为原先队头元素已经不是该元素所在区间范围中了if (i >= m)	cout << arr[q[head]] << endl;  //当判断过m个元素后才开始输出队头元素}return 0;}

 就以样例为例,说下过程:

一开始第一个数是16,发现16>0(因为arr[q[tail]]=arr[q[0]]=arr[0]=0),然后16的下标1经由q[++tail]存到了q[1]的位置,也是head所指的位置。然后遇到5,发现5<16,就tail--(tail从1变成了0),然后下一次循环,就由q[++tail],tail变成1, 5的下标2覆盖了16的下标1。

然后6,9都>5,分别让下标存到了q[2]=3,q[3]=4;在遇到9的时候,从16到9刚好满足m的长度,输出arr[q[head]],而head这里存放的正是由16~9这4个数中最小的数--5的下标2

然后遇到了5,发现5<9,tail--,tail变为了2,然后5<6,tail--,tail变为了1;然后下一次循环到else语句中,经由q[++tail],tail变为2, 5的下标存到了q[2]=5。而5~5这4个数中最小的元素仍是第一个5(下标为2的那个5),把这个5输出。

然后是13,这时,13的下标存到了q[3]=6,但是13的下标6-q[head]+1(6-2+1)=5>m,发现第一个5~13是的长度是5,而第一5并不在13所在的区间范围中,这时head++,往后移一位,head变为2,输出符合13所在区间的最小的数,即下标为5的那个5

同理然后就是q[4]=7,q[5]=8,直到遇到8(下标为9),发现经过tail的移动以及覆盖,q[2]=5,q[3]=9,但这时候9-q[head]+1(9-5+1)=5>m,这时第二个5并不是8所在范围中,这时head++,head=3;输出符合8所在区间的最小的数,即8

同理直到for遍历n次后

输出:

5 5 5 5 5 8 8

总之,队列q中存放的是,每个长度为m的组中最小值的下标

当然,head=1,tail=0,就是为了方便通过移动tail位置(用++tail)弹出队尾元素以及弹出队头元素(当第一个数据的下标输入进去后,tail通过自增,tail=1=head),就拿16和后面的5来说,16输入进去后,tail=head=1;但是5<16,这是tail--,变为0但是head仍然为1,后续经过++tail,让tail重新变为1,5的下标覆盖16的下标。

然后是&& head <= tail条件,这是为了防止已经把队列有效元素都弹完了,还继续弹。比如head=3时,如果没有该条件限制,当遇到一个整个数据中最新的数,比如1时,会不断弹,哪怕tail=2了,还在移动tail位置,此时等到再插入该数下标时,会把下标放在无效位置,因为head=3,q[3]以后才是有效位置

参考(来自学长们题解):

相关文章:

E-魔法猫咪(遇到过的题,做个笔记)

题解&#xff1a; 来自学长们思路&#xff1a; 其中一种正解是写单调队列。限制队列内的数单调递增&#xff0c;方法为每当新来的数据比当前队尾数据小时队 尾出列&#xff0c;直到能够插入当前值&#xff0c;这保证了队头永远是最小值。因此总体思路是队尾不断插入新值的同时 …...

keil创建工程 芯源半导体CW32F003E4P7

提前下载keil 安装步骤 1、下载CW32F003固件库 芯源半导体官网下载固件库 下载好后右键解压 CW32F003_StandardPeripheralLib_V1.5\IdeSupport\MDK 进入MDK文件夹 双击WHXY.CW32F003_DFP.1.0.4.pack安装固件库 点击next然后finish安装结束 keil创建工程 点击new uVision P…...

学习鸿蒙基础(12)

目录 一、网络json-server配置 &#xff08;1&#xff09;然后输入&#xff1a; &#xff08;2&#xff09;显示下载成功。但是输入json-server -v的时候。报错。 &#xff08;3&#xff09;此时卸载默认的json-server &#xff08;4&#xff09;安装和nodejs匹配版本的js…...

HTML5和CSS3笔记

一&#xff1a;网页结构(html)&#xff1a; 1.1&#xff1a;页面结构&#xff1a; 1.2&#xff1a;标签类型&#xff1a; 1.2.1&#xff1a;块标签&#xff1a; 1.2.2&#xff1a;行内标签&#xff1a; 1.2.3&#xff1a;行内块标签&#xff1a; 1.2.4&#xff1a;块标签与行…...

MHA高可用-解决MySQL主从复制的单点问题

目录 一、MHA的介绍 1&#xff0e;什么是 MHA 2&#xff0e;MHA 的组成 2.1 MHA Node&#xff08;数据节点&#xff09; 2.2 MHA Manager&#xff08;管理节点&#xff09; 3&#xff0e;MHA 的特点 4. MHA工作原理总结如下&#xff1a; 二、搭建 MySQL MHA 实验环境 …...

【多线程】震惊~这是我见过最详细的ReentrantLock的讲解

一.与synchronized相比ReentrantLock具有以下四个特点: 可中断&#xff1a;synchronized只能等待同步代码块执行结束&#xff0c;不可以中断&#xff0c;强行终断会抛出异常, 而reentrantlock可以调用线程的interrupt方法来中断等待&#xff0c;继续执行下面的代码。 在获取锁…...

分布式链路追踪与云原生可观测性

分布式链路追踪系统历史 Dapper, a Large-Scale Distributed Systems Tracing Infrastructure - Google Dapper&#xff0c;大规模分布式系统的跟踪系统大规模分布式系统的跟踪系统&#xff1a;Dapper设计给我们的启示 阿里巴巴鹰眼技术解密 - 周小帆京东云分布式链路追踪在金…...

CSS3新增的语法(三)【2D,3D,过渡,动画】

CSS3新增的语法&#xff08;三&#xff09;【2D,3D,过渡&#xff0c;动画】 10.2D变换10.1. 2D位移10.2. 2D缩放10.3. 2D旋转10.4. 2D扭曲&#xff08;了解&#xff09;10.5. 多重变换10.6. 变换原点 11. 3D变换11.1. 开启3D空间11.2. 设置景深11.3. 透视点位置11.4. 3D 位移11…...

Flutter应用在苹果商店上架前的准备工作与注意事项

引言 &#x1f680; Flutter作为一种跨平台的移动应用程序开发框架&#xff0c;为开发者提供了便利&#xff0c;使他们能够通过单一的代码库构建出高性能、高保真度的应用程序&#xff0c;同时支持Android和iOS两个平台。然而&#xff0c;完成Flutter应用程序的开发只是第一步…...

如何开启MySQL的binlog日志

1.启用远程连接&#xff1a; 如果你想要允许远程主机连接到MySQL服务器&#xff0c;需要进行以下步骤&#xff1a; 确保MySQL服务器的防火墙允许远程连接的流量通过。在MySQL服务器上&#xff0c;编辑MySQL配置文件&#xff08;一般是my.cnf&#xff09;&#xff0c;找到bind-…...

设计模式|状态机模式(State Machine Pattern)

文章目录 结构使用步骤示例使用状态机的场景常见面试题 状态机模式&#xff08;State Machine Pattern&#xff09;是一种用于描述对象的行为软件设计模式&#xff0c;属于行为型设计模式。在状态机模式中&#xff0c;对象的行为取决于其内部状态&#xff0c;并且在不同的状态下…...

Django源码之路由的本质(上)——逐步剖析底层执行流程

目录 1. 前言 2. 路由定义 3. 路由定义整体源码分析 3.1 partial实现path函数调用 3.2 图解_path函数 3.3 最终 4.URLPattern和Pattern的简单解析 5. 小结 1. 前言 在学习Django框架的时候&#xff0c;我们大多时候都只会使用如何去开发项目&#xff0c;对其实现流程并…...

基于深度学习的植物叶片病毒识别系统(网页版+YOLOv8/v7/v6/v5代码+训练数据集)

摘要&#xff1a;本文深入研究了基于YOLOv8/v7/v6/v5的植物叶片病毒识别系统&#xff0c;核心采用YOLOv8并整合了YOLOv7、YOLOv6、YOLOv5算法&#xff0c;进行性能指标对比&#xff1b;详述了国内外研究现状、数据集处理、算法原理、模型构建与训练代码&#xff0c;及基于Strea…...

Native Instruments Kontakt 7 for Mac v7.9.0 专业音频采样

Native Instruments Kontakt 7是一款强大的软件采样器&#xff0c;它允许用户从各种来源采样音频并进行编辑和处理。它包含大量预设采样库&#xff0c;包括乐器、合成器、鼓组和声音效果等。此外&#xff0c;Kontakt 7还允许用户创建自己的采样库&#xff0c;以便根据自己的需要…...

yolov8训练流程

训练代码 from ultralytics import YOLO# Load a model model YOLO(yolov8n.yaml) # build a new model from YAML model YOLO(yolov8n.pt) # load a pretrained model (recommended for training) model YOLO(yolov8n.yaml).load(yolov8n.pt) # build from YAML and tr…...

Java基础学习: Forest - 极简 HTTP 调用 API 框架

文章目录 一、介绍参考&#xff1a; 一、介绍 Forest是一个开源的Java HTTP客户端框架&#xff0c;专注于简化HTTP客户端的访问。它是一个高层的、极简的轻量级HTTP调用API框架&#xff0c;通过Java接口和注解的方式&#xff0c;将复杂的HTTP请求细节隐藏起来&#xff0c;使HT…...

Pandas Dataframe合并连接Join和merge 参数讲解

文章目录 函数与参数分析otheronhowlsuffix, rsuffix, suffixesleft_index, right_index 函数与参数分析 在pandas中主要有两个函数可以完成table之间的join Join的函数如下&#xff1a; DataFrame.join(other, onNone, how‘left’, lsuffix‘’, rsuffix‘’, sortFalse, v…...

ABC318 F - Octopus

解题思路 对于每个宝藏维护个区间&#xff0c;答案一定在这些区间中对于每个区间的端点由小到大排序对于每个点进行判断&#xff0c;若当前位置合法&#xff0c;则该点一定为一个右端点则该点到前一个端点之间均为合法点若前一个点不合法&#xff0c;则一定是某一个区间限制的…...

Docker实战教程 第3章 Dockerfile

4-2 通过dockerfile制作镜像 需求 制作一个具有ping ip ifconfig vim 这些命令工具的一个nginx镜像&#xff0c;通过dockerfile完成STEP1 : 写一个Dockerfile FROM nginx # 基于一个基础镜像 RUN lsstep2 docker build . -f 指定使用的dockerfile来生成镜像-t 指定镜像名…...

JSON在量化交易系统中的应用

JSON在量化交易系统中的应用场景 数据传输和存储&#xff1a;JSON可以将交易数据以结构化的方式进行编码&#xff0c;并将其转换为字符串进行传输和存储。这样可以方便地在不同的系统之间传递数据&#xff0c;并且可以保持数据的完整性和一致性。 API通信&#xff1a;量化交易…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...