蓝桥杯每日一题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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/140014.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

经典题记录 字符串相加/相乘

1. LeetCode 415 字符串相加 代码一&#xff1a;代码简短&#xff0c;但需要借助额外的一个string来保存结果&#xff0c;更占用内存。 class Solution { public:string addStrings(string num1, string num2) {string ans"";int size1num1.size();int size2num2.si…

qt 6知识集

1.Use multi-arg instead [clazy-qstring-arg] 存在过个arg&#xff0c;连写形式如下&#xff1a; QString("%1 %2").arg(a).arg(b);QString("%1 %2").arg(a, b); // one less temporary heap allocation详见参考文献[1]。 2.widget运行后正常打开却看不…

基于Java的酒店管理系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容&#xff1a;毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 项目介绍…

Three.js后期处理简明教程

后期处理&#xff08;Post Processing&#xff09;通常是指对 2D 图像应用某种效果或滤镜。 在 THREE.js 中我们有一个包含一堆网格物体的场景。 我们将该场景渲染为 2D 图像。 通常&#xff0c;该图像会直接渲染到画布中并显示在浏览器中&#xff0c;但我们可以将其渲染到渲染…

双向链表的实现(增删查改)——最好理解的链表

双向链表的实现 一&#xff0c;双向链表的特点二&#xff0c;双向链表的结构三&#xff0c;双向链表的内容实现3.1创建node节点3.2初始化3.3打印3.4插入3.4.1尾插3.4.2头插3.4.3在pos位置上插入 3.5删除3.5.1尾删3.5.2头删3.5.3删除pos位置上的数据 四&#xff0c;调试技巧&…

html页面仿word文档样式(vue页面也适用)

目录 文章title&#xff1a; 标题&#xff1a; 正文&#xff1a; 完整代码&#xff1a; 页面效果&#xff1a; 文章title&#xff1a; <div><h3 style"display: flex;justify-content: center; align-items: center; color: #000;">实验室招新报名公…

【100天精通Python】Day69:Python可视化_实战:导航定位中预测轨迹和实际轨迹的3D动画,示例+代码

目录 1. 预测的3D轨迹和实际轨迹的动画图&#xff0c;同时动态更新 2 真值轨迹设置为静态的&#xff0c;预测轨迹不断更新 3 网格的三维坐标系有旋转运动&#xff0c;以此全方位展示预测轨迹和真值轨迹之间的空间关系 1. 预测的3D轨迹和实际轨迹的动画图&#xff0c;同时动态更…

Nginx 防止跨站脚本 Cross-Site Scripting (XSS)

1、修改 nginx 配置 在 nginx.conf 配置文件中&#xff0c;增加如下配置内容&#xff1a; add_header X-XSS-Protection "1; modeblock";X-XSS-Protection 的字段有三个可选配置值&#xff0c;说明如下&#xff1a; 0&#xff1a; 表示关闭浏览器的XSS防护机制&…

ad18学习笔记十一:显示和隐藏网络、铺铜

如何显示和隐藏网络&#xff1f; Altium Designer--如何快速查看PCB网络布线_ad原理图查看某一网络的走线_辉_0527的博客-CSDN博客 AD19(Altium Designer)如何显示和隐藏网络 如何显示和隐藏铺铜&#xff1f; Altium Designer 20在PCB中显示或隐藏每层铺铜-百度经验 AD打开与…

怎么将自己的Maven项目上传到Maven中央仓库/Maven阿里云云效仓库

前言 对于工作了多年的老程序员来说&#xff0c;往往会总结出一些比较好用的开发工具包。那么如果把这些好的工具插件共享出来供大家快速的使用呢&#xff0c;最好的方式就是将这些工具插件上传到Maven中央仓库/Maven阿里云云效仓库&#xff0c;这样&#xff0c;有需要用到这些…

八大排序(一)冒泡排序,选择排序,插入排序,希尔排序

一、冒泡排序 冒泡排序的原理是&#xff1a;从左到右&#xff0c;相邻元素进行比较。每次比较一轮&#xff0c;就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。 以从小到大排序为例&#xff0c;第一轮比较后&#xff0c;所有数中最大的那个数就会浮…

verilog学习笔记(1)module实例化

兜兜转转又回来学硬件了&#xff0c;哎&#xff0c;命啊&#xff01; 我的答案&#xff08;有bug&#xff09;&#xff1a; module top_module ( input a, input b, output out );wire w1;wire w2;wire w3;mod_a mod_a_inst1(.in1(w1),.in2(w2),.out(w3) );assign w1 a…

基于微信小程序的房屋租赁系统设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言运行环境说明用户微信小程序端的主要功能有&#xff1a;户主微信小程序端的主要功能有&#xff1a;管理员的主要功能有&#xff1a;具体实现截图详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考论文…

解决 Github port 443 : Timed out

解决方法 打开代理页面 打开 设置 --> 网络与Internet --> 查找代理 记录下当前系统代理的 IP 地址和端口号 如上图所示&#xff0c;地址与端口号为&#xff1a;127.0.0.1:7890 注意修改成自己的IP和端口号 git config --global http.proxy http://127.0.0.1:7890 gi…

Spring面试题12:Spring中IOC的优缺点是什么?IOC依赖注入方式有哪些

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:Spring中IOC的优缺点是什么? IOC(Inversion of Control,控制反转)是Spring框架的一个重要特性,它实现了对象的创建和依赖关系的管理的反转。…

【Linux】Linux环境配置安装

目录 一、双系统&#xff08;特别不推荐&#xff09; 安装双系统的缺点&#xff1a; 安装双系统优点&#xff08;仅限老手&#xff09;&#xff1a; 二、虚拟机centos7镜像&#xff08;较为推荐推荐&#xff09; 虚拟机的优点&#xff1a; 虚拟机的缺点&#xff1a; ​ …

6年Android开发前10月的总结,写给正在求职的安卓开发

进入大厂工作对许多人来说已经是一种挑战&#xff0c;但只要充分准备&#xff0c;很多问题都可以逐步解决。当然&#xff0c;运气也起到了一定的作用&#xff0c;但最终还是与自身的努力密不可分。运气是实力的一部分&#xff0c;因为自助者天助。 每到10月进行总结时&#xff…

数据结构与算法(二)

文章目录 数据结构与算法(二)1 时间复杂度、空间复杂度、排序算法和二分法1.1 简单的排序算法1.2 二分查找2 异或运算、进一步认识对数器的重要性2.1 不用额外变量交换两个数的值2.2 不用额外变量交换数组中两个数的值2.3 一个数组中有一种数出现了奇数次,其他数都出现了偶数…

读写分离MySQL

利用Mycat控制后台数据库的读写分离和负载均衡 利用主从复制思想,实现读写分离,主库写,从库读 从库最好不要写,因为从库写入的数据不能同步到主库,只有主库写的数据才能同步到从库 balance属性值对应的含义(负载均衡) 一主一从读写分离的弊端 主节点Master宕机以后,业务系统…

docker 操作redis

1查看容器 2进入容器 exec表示在运行的容器中执行命令it表示以终端交互的方式执行命令/bin/bash表示需要指定的命令 3进入容器后可通过redis-cli命令连接容器内的redis服务器&#xff0c;可通过set创建变量&#xff0c;get获取变量的值 4key * 查看所有key 通过ping 查看redi…