当前位置: 首页 > 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;量化交易…...

x-cmd-pkg | broot 是基于 Rust 开发的一个终端文件管理器

简介 broot 是基于 Rust 开发的一个终端文件管理器&#xff0c;它设计用于帮助用户在终端中更轻松地管理文件和目录&#xff0c;使用树状视图探索文件层次结构、操作文件、启动操作以及定义您自己的快捷方式。 同时它还集成了 ls, tree, find, grep, du, fzf 等工具的常用功能…...

设置asp.net core WebApi函数请求参数可空的两种方式

以下面定义的asp.net core WebApi函数为例&#xff0c;客户端发送申请时&#xff0c;默认三个参数均为必填项&#xff0c;不填会报错&#xff0c;如下图所示&#xff1a; [HttpGet] public string GetSpecifyValue(string param1,string param2,string param3) {return $"…...

Vue.js组件精讲 开篇:Vue.js的精髓——组件

写在前面 Vue.js&#xff0c;无疑是当下最火热的前端框架 Almost&#xff0c;而 Vue.js 最精髓的&#xff0c;正是它的组件与组件化。写一个 Vue 工程&#xff0c;也就是在写一个个的组件。 业务场景是千变万化的&#xff0c;而不变的是 Vue.js 组件开发的核心思想和使用技巧…...

R语言中的常用数据结构

目录 R对象的基本类型 R对象的属性 R的数据结构 向量 矩阵 数组 列表 因子 缺失值NA 数据框 R的数据结构总结 R语言可以进行探索性数据分析&#xff0c;统计推断&#xff0c;回归分析&#xff0c;机器学习&#xff0c;数据产品开发 R对象的基本类型 R语言对象有五…...

基于Python的微博旅游情感分析、微博舆论可视化系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

机器学习的模型校准

背景知识 之前一直没了解过模型校准是什么东西&#xff0c;最近上班业务需要看了一下&#xff1a; 模型校准是指对分类模型进行修正以提高其概率预测的准确性。在分类模型中&#xff0c;预测结果通常以类别标签形式呈现&#xff08;例如&#xff0c;0或1&#xff09;&#xf…...

0.17元的4位数码管驱动芯片AiP650,支持键盘,还是无锡国家集成电路设计中心某公司的

推荐原因&#xff1a;便宜的4位数码管驱动芯片 只要0.17元&#xff0c;香吗&#xff1f;X背景的哦。 2 线串口共阴极 8 段 4 位 LED 驱动控制/7*4 位键盘扫描专用电路 AIP650参考电路图 AIP650引脚定义...

【C++】编程规范之内存规则

在高质量编程中&#xff0c;内存管理是一个至关重要的方面。主要有以下原则&#xff1a; 内存分配后需要检查是否成功&#xff1a;内存分配可能会失败&#xff0c;特别是在内存紧张的情况下。因此&#xff0c;在分配内存后&#xff0c;应该检查分配是否成功。 int* ptr new …...

并发编程之线程池的应用以及一些小细节的详细解析

线程池在实际中的使用 实际开发中&#xff0c;最常用主要还是利用ThreadPoolExecutor自定义线程池&#xff0c;可以给出一些关键的参数来自定义。 在下面的代码中可以看到&#xff0c;该线程池的最大并行线程数是5&#xff0c;线程等候区&#xff08;阻塞队列)是3&#xff0c;即…...

基于JSP的农产品供销服务系统

背景 互联网的迅猛扩张彻底革新了全球各类组织的运营模式。自20世纪90年代起&#xff0c;中国的政府机关和各类企业便开始探索利用网络系统来处理管理事务。然而&#xff0c;早期的网络覆盖范围有限、用户接受度不高、互联网相关法律法规不完善以及技术开发不够成熟等因素&…...