当前位置: 首页 > 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 -…...

Android Perfetto 系列 6:为什么是 120Hz?高刷新率的优势与挑战

Android Perfetto 系列 6&#xff1a;为什么是 120Hz&#xff1f;高刷新率的优势与挑战本文是 Android Perfetto 系列的第六篇&#xff0c;主要介绍 Android 设备上 120Hz 刷新率的相关知识。如今&#xff0c;120Hz 已成为 Android 旗舰手机的标配&#xff0c;本文将讨论高刷新…...

后端/全栈/架构师转战AI大模型开发:可落地规划(建议收藏)

如果你本身是后端、全栈或架构师出身&#xff0c;就意味着你已经手握一套扎实的“确定性系统”构建能力——分布式部署、高并发处理、数据库事务管控、系统稳定性保障&#xff0c;这些都是你转型AI大模型开发的核心底牌&#xff0c;也是纯算法出身从业者难以快速补齐的短板。 而…...

例子-子网划分问题

...

终极Chrome全页截图指南:一键保存完整网页内容的高效方案

终极Chrome全页截图指南&#xff1a;一键保存完整网页内容的高效方案 【免费下载链接】full-page-screen-capture-chrome-extension One-click full page screen captures in Google Chrome 项目地址: https://gitcode.com/gh_mirrors/fu/full-page-screen-capture-chrome-ex…...

保姆级教程:MogFace人脸检测模型-large快速上手,无需代码轻松体验

保姆级教程&#xff1a;MogFace人脸检测模型-large快速上手&#xff0c;无需代码轻松体验 1. 认识MogFace人脸检测模型 1.1 什么是MogFace MogFace是目前最先进的人脸检测方法之一&#xff0c;在Wider Face六项榜单上长期保持领先地位。这个模型通过三个创新点显著提升了检测…...

AOP 失效的 7 种死法与复活指南

还是那句话&#xff0c;知识是一个返回的过程&#xff0c;追一句&#xff1a;时间出真知今天我们要聊的是一个“灵异事件”频发的领域——Spring AOP 失效。你是不是也经历过这种崩溃&#xff1a;“明明加了 Transactional&#xff0c;为什么数据库报错不回滚&#xff1f;” “…...

用Python的powerlaw库分析游戏付费数据:从‘鲸鱼玩家’到长尾分布,手把手教你做实战分析

用Python的powerlaw库解析游戏付费行为&#xff1a;从数据清洗到商业决策全流程 游戏行业的数据分析师们常常面临一个经典问题&#xff1a;如何理解玩家付费行为背后的数学规律&#xff1f;当我们打开一份付费数据报表&#xff0c;往往会发现少数"鲸鱼玩家"贡献了绝…...

Qwen3-VL-Reranker-8B应用场景:科研数据集图文代码混合检索

Qwen3-VL-Reranker-8B应用场景&#xff1a;科研数据集图文代码混合检索 1. 科研检索的痛点与解决方案 科研工作者在日常研究中经常面临这样的困境&#xff1a;手头有大量包含文本、图像、代码片段的研究资料&#xff0c;想要快速找到相关内容却异常困难。传统的文本检索工具只…...

Virtuoso ADE仿真避坑指南:你的时钟占空比测对了吗?详解dutyCycle函数threshold参数设置

Virtuoso ADE仿真避坑指南&#xff1a;时钟占空比测量的关键参数解析 在模拟电路设计中&#xff0c;时钟信号的占空比精度往往直接影响系统性能。许多工程师虽然熟悉Virtuoso ADE的基础操作&#xff0c;却在自动测量占空比时遭遇"数据看起来合理但实际存在偏差"的困境…...

图像超分新思路:拆解SCNet的‘空间移位’操作,看它如何用零参数实现3x3卷积的效果

图像超分辨率革命&#xff1a;零参数空间移位如何颠覆传统卷积设计 当你在手机相册里翻出一张十年前的老照片&#xff0c;是否曾幻想过能一键修复那些模糊的像素&#xff1f;这正是图像超分辨率技术试图解决的难题。传统方法依赖计算密集的33卷积&#xff0c;而SCNet提出的&quo…...