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

蓝桥杯每日一题2023.9.23

4961. 整数删除 - AcWing题库

题目描述

 分析

注:如果要进行大量的删除操作可以使用链表

动态求最小值使用堆,每次从堆中取出最小值的下标然后在链表中删除

注意long long

代码解释:

	while(k --){auto t = q.top();q.pop();res = t.first;i = t.second;if(res != v[i])q.push({v[i], i});else del(i);	}

eg. 2 3 4此时这三个数的下标分别为1 2 3

第一步:在q的队列中加入2, 3, 4,第一次k --进行del操作,使v[2] == 5

第二部:q.top() == 3发现3对应下标为2, v[2]原本为3,但是上一步使其变为了5,故此时需要重新将5加入队列,当然,此时k不算进行了一次操作,需要k ++(因为这一步只是将上一步两边加数的操作进行了完善)

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
typedef long long ll;
typedef pair<ll, ll> PII;
priority_queue<PII, vector<PII>, greater<PII>>q;
ll n, k, v[N], l[N], r[N];
void del(ll x)
{r[l[x]] = r[x], l[r[x]] = l[x];v[l[x]] += v[x], v[r[x]] += v[x];
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> k;r[0] = 1, l[n + 1] = n;//初始化左右端点的下标,将0后的下标赋于1,将n + 1左边的下标赋予n for(int i = 1; i <= n; i ++){cin >> v[i];//下标i对应的值为v[i]l[i] = i - 1;//建立双链表 r[i] = i + 1; q.push({v[i], i});//将值和对应下标存入优先队列 }while(k --){auto t = q.top();q.pop();ll res = t.first;ll i = t.second;if(res != v[i]){q.push({v[i], i});k ++;}else del(i);	}for(int i = r[0]; i != n + 1; i = r[i]){cout << v[i] << ' ';}cout << '\n';return 0;
}

相关文章:

蓝桥杯每日一题2023.9.23

4961. 整数删除 - AcWing题库 题目描述 分析 注&#xff1a;如果要进行大量的删除操作可以使用链表 动态求最小值使用堆&#xff0c;每次从堆中取出最小值的下标然后在链表中删除 注意long long 代码解释&#xff1a; while(k --){auto t q.top();q.pop();res t.first;i…...

C语言数组和指针笔试题(三)(一定要看)

目录 字符数组四例题1例题2例题3例题4例题5例题6例题7 结果字符数组五例题1例题2例题3例题4例题5例题6例题7结果字符数组六例题1例题2例题3例题4例题5例题6例题7 结果 感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接 &#x1f412;&#x1f412;&#x1f412;个…...

leetcode11 盛水最多的容器

题目 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 示例 输入&#xff1a;[1,8,6,2,5,4,8,…...

进入数据结构的世界

数据结构和算法的概述 一、什么是数据结构二、什么是算法三、如何去学习数据结构和算法四、算法的时间复杂度和空间复杂度4.1 算法效率4.2 大O的渐进表示法4.3 时间复杂度4.4 空间复杂度4.5 常见复杂度对比 一、什么是数据结构 数据结构是计算机存储、组织数据的方式。&#x…...

stm32之看门狗

STM32 有两个看门狗&#xff0c;独立看门狗和窗口看门狗&#xff0c;独立看门狗又称宠物狗&#xff0c;窗 口看门狗又称警犬。可用来检测和解决由软件错误引起的故障。两个看门狗的原理都是当计数器达到给定的超时值时&#xff0c;产生系统复位&#xff0c;对于窗口型看门狗同…...

纤维蛋白单体(FM)介绍

纤维蛋白单体&#xff08;FM&#xff09;是血栓形成的早期产物&#xff0c;是纤维蛋白原&#xff08;Fibrinogen&#xff0c;Fbg&#xff09;在凝血酶&#xff08;Thrombin&#xff09;的作用下&#xff0c;脱掉肽A&#xff08;Fibrinopeptide A&#xff0c;Fp A&#xff09;与…...

知识图谱实战导论:从什么是KG到LLM与KG/DB的结合实战

前言 本文侧重讲解&#xff1a; 什么是知识图谱LLM与langchain/数据库/知识图谱的结合应用 比如&#xff0c;虽说基于知识图谱的问答 早在2019年之前就有很多研究了&#xff0c;但谁会想到今年KBQA因为LLM如此突飞猛进呢 第一部分 知识图谱入门导论 //待更.. 第二部分 LLM与…...

第5章 会话与会话技术

第5章 会话与会话技术 一. 单选题&#xff08;共5题&#xff0c;50分&#xff09;二. 判断题&#xff08;共5题&#xff0c;50分&#xff09; 一. 单选题&#xff08;共5题&#xff0c;50分&#xff09; (单选题) 阅读下面代码&#xff1a; Book book BookDB.getBook(id)…...

IDEA2023新UI回退老UI

idea2023年发布了新UI&#xff0c;如下所示 但是用起来真心不好用&#xff0c;各种位置也是错乱&#xff0c;用下面方法可以回退老UI...

ElasticSearch(三)

1.数据聚合 聚合&#xff08;aggregations&#xff09;可以让我们极其方便的实现对数据的统计、分析、运算。例如&#xff1a; 什么品牌的手机最受欢迎&#xff1f; 这些手机的平均价格、最高价格、最低价格&#xff1f; 这些手机每月的销售情况如何&#xff1f; 实现这些…...

【LinkedHashMap】146. LRU 缓存

146. LRU 缓存 解题思路 与普通的 HashMap 不同&#xff0c;LinkedHashMap 会保持元素的有序性。这可以在某些情况下提供更可预测的迭代顺序直接获取元素 因为使用到该元素 将该元素重新放入队尾 表示最近使用该元素写入元素&#xff0c;首先如果该元素原来存在 那么需要将ke…...

Opencv-python去图标与水印方案实践

RGB色彩模式是工业界的一种颜色标准&#xff0c;是通过对红&#xff08;R&#xff09;、绿&#xff08;G&#xff09;、蓝&#xff08;B&#xff09;三个颜色通道的变化以及它们相互之间的叠加来得到各式各样的颜色的&#xff0c;RGB即是代表红、绿、蓝三个通道的颜色&#xff…...

自己写过比较蠢的代码:从失败中学习的经验

文章目录 引言1. 代码没有注释2. 长函数和复杂逻辑3. 不恰当的变量名4. 重复的代码5. 不适当的异常处理6. 硬编码的敏感信息7. 没有单元测试结论 &#x1f389; 自己写过比较蠢的代码&#xff1a;从失败中学习的经验 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒&#x1f379;✨博客主页&a…...

C语言 cortex-A7核 点LED灯 (附 汇编实现、使用C语言 循环实现、使用C语言 封装函数实现【重要、常用】)

1 汇编实现 text global _start start: ************** LED1点灯 ---> PE10 **************/ ************** RCC章节初始化 **************/ CC_INIT:1.使能GPIOE组控制器&#xff0c;通过RCC_MP_AHB4ENSETR寄存器设置GPIOE组使能0x50000A28[4] 1ldr r0,0x50000A28 准…...

LABVIEW 实战案例1--温度报警系统

图1 温度报警系统前面板 图2 温度报警系统后面板...

【力扣】292. Nim 游戏

题目描述 你和你的朋友&#xff0c;两个人一起玩 Nim 游戏&#xff1a; 桌子上有一堆石头。你们轮流进行自己的回合&#xff0c; 你作为先手 。每一回合&#xff0c;轮到的人拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。 假设你们每一步都是最优解。请编写一个函数…...

IAP固件升级分几步?(Qt上位机、)

前言 这周一直想做一个IAP固件升级的上位机&#xff0c;然后把升级流程全都搞懂 有纰漏请指出&#xff0c;转载请说明。 学习交流请发邮件 1280253714qq.com IAP原理 IAP的原理我就不多赘述了&#xff0c;这里贴上几位大佬的文章 STM32CubeIDE IAP原理讲解&#xff0c;及U…...

Otter改造 增加springboot模块和HTTP调用功能

环境搭建 & 打包 环境搭建&#xff1a; 进入 $otter_home/lib 目录执行&#xff1a;bash install.sh 打包&#xff1a; 进入$otter_home目录执行&#xff1a;mvn clean install -Dmaven.test.skip -Denvrelease发布包位置&#xff1a;$otter_home/target 项目背景 阿里…...

Vue.js vs React:哪一个更适合你的项目?

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…...

Debian环境下搭建STM32开发环境

1. 安装交叉编译工具&#xff0c;解压gcc-arm-none-eabi-10.3-2021.10-x86_64-linux.tar.bz2&#xff0c;并且把交叉编译环境添加到path路径。 2.安装下载工具驱动和下载工具 # 安装下载工具openocd sudo apt -y install openocd 3.下载测试 sudo openocd -f cmsis-dap.cfg -…...

【Python 3.15 JIT终极指南】:20年CPython核心开发者亲授,从零部署到性能翻倍的5个关键跃迁

第一章&#xff1a;Python 3.15 JIT的诞生背景与核心设计哲学 Python 长期以来以开发效率和生态丰富性见长&#xff0c;但其解释执行模型在 CPU 密集型场景下始终面临性能瓶颈。CPython 的字节码解释器虽稳定可靠&#xff0c;却缺乏运行时优化能力&#xff1b;而第三方方案&…...

WavePWM库:嵌入式LED正弦调光算法与实现

1. WavePWM库概述&#xff1a;正弦波形LED调光的底层实现原理与工程应用 WavePWM是一个面向嵌入式LED驱动场景的轻量级波形PWM计算库&#xff0c;其核心价值不在于直接控制硬件引脚&#xff0c;而在于 以确定性数学模型生成高保真度的正弦&#xff08;或类正弦/指数&#xff0…...

17 种 RAG 优化策略

RAG 完整解析 本文适合小白入门&#xff0c;全程用「公司员工手册查病假」为统一实例&#xff0c;清晰讲解 RAG 是什么、工作流程&#xff0c;以及 17 种 RAG 优化策略&#xff08;含标准英文术语&#xff09;&#xff0c;所有内容可直接复制用于分享&#xff0c;实例均精确到具…...

示波器安全操作与高压测量实践指南

示波器安全使用指南&#xff1a;从基础操作到高压测量实践1. 示波器使用安全概述示波器作为电子工程师的核心调试工具&#xff0c;其正确使用直接关系到测量结果的准确性和操作人员的人身安全。在实际工程应用中&#xff0c;约35%的测量事故源于不规范的示波器操作&#xff0c;…...

Nginx 简单使用配置

配置 user nginx; worker_processes auto;error_log /var/log/nginx/error.log notice; pid /var/run/nginx.pid;events {worker_connections 1024; }http {include /etc/nginx/mime.types;default_type application/octet-stream;log_format main $remote…...

颠覆PDF转换体验:Marker无缝实现25页/秒全场景文档格式精准迁移

颠覆PDF转换体验&#xff1a;Marker无缝实现25页/秒全场景文档格式精准迁移 【免费下载链接】marker 一个高效、准确的工具&#xff0c;能够将 PDF 和图像快速转换为 Markdown、JSON 和 HTML 格式&#xff0c;支持多语言和复杂布局处理&#xff0c;可选集成 LLM 提升精度&#…...

CentOS7下SSD性能调优实战:iostat与dd命令的黄金组合

CentOS7下SSD性能调优实战&#xff1a;iostat与dd命令的黄金组合 在当今数据驱动的时代&#xff0c;存储性能往往成为系统瓶颈的关键所在。对于使用CentOS7系统的运维工程师来说&#xff0c;如何充分释放SSD硬件的性能潜力&#xff0c;是一个既具挑战性又充满成就感的技术课题。…...

你用AI写代码时,是不是总觉得“它懂语法,却搞不定真实工程”?Composer 2的答案在这里

很多开发者都有过这种体验&#xff1a;把一个真实项目需求甩给AI&#xff0c;它能秒出语法完美的代码片段&#xff0c;可一到大型代码库、遗留系统、多文件联动的时候&#xff0c;就开始原地打转。改了半天核心逻辑没动&#xff0c;引入新问题&#xff0c;或者干脆在长链条任务…...

如何高效使用抖音批量下载工具:3个技巧让视频收集效率提升90%

如何高效使用抖音批量下载工具&#xff1a;3个技巧让视频收集效率提升90% 【免费下载链接】douyin-downloader 项目地址: https://gitcode.com/GitHub_Trending/do/douyin-downloader 在短视频内容爆炸的时代&#xff0c;抖音作为国内领先的内容平台&#xff0c;每天产…...

PyTorch实战(38)——深度学习模型可解释性

PyTorch实战&#xff08;38&#xff09;——深度学习模型可解释性0. 前言1. PyTorch 模型可解释性2. 训练手写数字分类器3. 可视化模型卷积核4. 可视化特征图小结系列链接0. 前言 在本专栏中&#xff0c;我们已经构建了多种深度学习模型来完成不同任务&#xff0c;包括手写数字…...