Acwing---839. 模拟堆

模拟堆

  • 1.题目
  • 2.基本思想
  • 3.代码实现

1.题目

维护一个集合,初始时集合为空,支持如下几种操作:

  1. I x,插入一个数 x;
  2. PM,输出当前集合中的最小值;
  3. DM,删除当前集合中的最小值(数据保证此时的最小值唯一);
  4. D k,删除第 k 个插入的数;
  5. C k x,修改第 k 个插入的数,将其变为 x;

现在要进行 N次操作,对于所有第 2 个操作,输出当前集合的最小值。

输入格式
第一行包含整数 N N N

接下来 N N N 行,每行包含一个操作指令,操作指令为 I xPMDMD kC k x 中的一种。

输出格式
对于每个输出指令 PM,输出一个结果,表示当前集合中的最小值。

每个结果占一行。

数据范围
1 ≤ N ≤ 1 0 5 1≤N≤10^5 1N105

− 1 0 9 ≤ x ≤ 1 0 9 −10^9≤x≤10^9 109x109

数据保证合法。 数据保证合法。 数据保证合法。

输入样例:

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例:

-10
6

2.基本思想

在这里插入图片描述

3.代码实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.Scanner;public class _839模拟堆 {static int N = 100010;static int[] h = new int[N];//h代表heap(堆)static int[] ph = new int[N];//ph(point->heap)可以获得第几个插入的元素现在在堆的那个位置static int[] hp = new int[N]; //hp(heap->point)可以获得在堆的第n个元素存的是第几个插入的元素static int size, m;static void heap_swap(int a, int b) {//交换在heap中位置分别为a,b的两个元素swap(ph, hp[a], hp[b]);//第一步交换蓝色线swap(hp, a, b);//绿线swap(h, a, b);//真实值}static private void swap(int[] arr, int a, int b) {int temp = arr[a];arr[a] = arr[b];arr[b] = temp;}private static void down(int u) {//当前堆的元素下沉int min = u;if (u * 2 <= size && h[u * 2] < h[min]) min = u * 2;if (u * 2 + 1 <= size && h[u * 2 + 1] < h[min]) min = u * 2 + 1;if (u != min) {heap_swap(min, u);down(min);}}private static void up(int u) {while (u / 2 > 0 && h[u / 2] > h[u]) {heap_swap(u / 2, u);u /= 2;}}public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());while (n-- > 0) {String[] s = br.readLine().split(" ");String opt = s[0];if (opt.equals("I")) {int x = Integer.parseInt(s[1]);size++;m++;h[size] = x;ph[m] = size;hp[size] = m;up(size);} else if (opt.equals("PM")) System.out.println(h[1]);else if (opt.equals("DM")) {heap_swap(1, size);size--;down(1);} else if (opt.equals("D")) {int k = Integer.parseInt(s[1]);int u = ph[k];heap_swap(u, size);size--;down(u);up(u);} else if (opt.equals("C")) {int k = Integer.parseInt(s[1]);int x = Integer.parseInt(s[2]);int u = ph[k];h[u] = x;down(u);up(u);}}}
}

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

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

相关文章

蓝桥杯-X图形

问题描述 给定一个字母矩阵。一个 X 图形由中心点和由中心点向四个 45度斜线方向引出的直线段组成&#xff0c;四条线段的长度相同&#xff0c;而且四条线段上的字母和中心点的字母相同。 一个 X 图形可以使用三个整数 r,c,L 来描述&#xff0c;其中 r,c 表示中心点位于第 r 行…

Vue源码系列讲解——虚拟DOM篇【二】(Vue中的DOM-Diff)

目录 1. 前言 2. patch 3. 创建节点 4. 删除节点 5. 更新节点 6. 总结 1. 前言 在上一篇文章介绍VNode的时候我们说了&#xff0c;VNode最大的用途就是在数据变化前后生成真实DOM对应的虚拟DOM节点&#xff0c;然后就可以对比新旧两份VNode&#xff0c;找出差异所在&…

基于大语言模型的AI Agents

代理&#xff08;Agent&#xff09;指能自主感知环境并采取行动实现目标的智能体。基于大语言模型&#xff08;LLM&#xff09;的 AI Agent 利用 LLM 进行记忆检索、决策推理和行动顺序选择等&#xff0c;把Agent的智能程度提升到了新的高度。LLM驱动的Agent具体是怎么做的呢&a…

java_error_in_pycharm.hprof文件是什么?能删除吗?

java_error_in_pycharm.hprof文件是什么&#xff1f;能删除吗&#xff1f; &#x1f335;文章目录&#x1f335; &#x1f333;引言&#x1f333;&#x1f333;hprof格式文件介绍&#x1f333;&#x1f333;java_error_in_pycharm.hprof文件什么情况下能删除&#x1f333;&…

Docker-Learn(二)保存、导入、使用Docker镜像

1.保存镜像 根据上一节内容&#xff0c;将创建好镜像进行保存&#xff0c;需要退出当前的已经在运行的docer命令行中断里面&#xff0c;可以通过在终端里面输入指令exit或者按下键盘上的 ctrlD建退出&#xff1a; 回到自己的终端里面&#xff0c;输入指令&#xff1a; docker…

跟着cherno手搓游戏引擎【23】项目维护、2D引擎之前的一些准备

项目维护&#xff1a; 修改文件结构&#xff1a; 头文件自己改改就好了 创建2DRendererLayer&#xff1a; Sandbox2D.h: #pragma once #include "YOTO.h" class Sandbox2D :public YOTO::Layer {public:Sandbox2D();virtual ~Sandbox2D() default;virtual void O…

微软.NET6开发的C#特性——类、结构体和联合体

我是荔园微风&#xff0c;作为一名在IT界整整25年的老兵&#xff0c;看到不少初学者在学习编程语言的过程中如此的痛苦&#xff0c;我决定做点什么&#xff0c;下面我就重点讲讲微软.NET6开发人员需要知道的C#特性&#xff0c;然后比较其他各种语言进行认识。 C#经历了多年发展…

第77讲用户管理功能实现

用户管理功能实现 前端&#xff1a; views/user/index.vue <template><el-card><el-row :gutter"20" class"header"><el-col :span"7"><el-input placeholder"请输入用户昵称..." clearable v-model"…

Linux第43步_移植ST公司uboot的第4步_uboot测试

uboot移植结束后&#xff0c;需要进行测试。 1、烧录程序 1)、将STM32MP157开发板的网络接口与路由器的网络接口通过网线连接起来。 2)、将开发板的串口和电脑通过USB线连接起来。 3)、将开发板的USB OTG接口和电脑通过USB线连接起来。 4)、将开发板上拨码开关拨到“000”…

「Linux」用户操作

root用户 su&#xff1a;切换账户 语法&#xff1a;su [–] [用户名] -&#xff1a;可选&#xff0c;表示是否在切换用户后加载环境变量&#xff0c;建议带上用户名&#xff1a;表示要切换的用户&#xff0c;省略时表示切换到root切换用户后&#xff0c;通过exit命令退回上一个…

LocalAI 部署(主要针对 mac m2 启动)

LocalAI 部署 介绍 LocalAI 是免费的开源 OpenAI 替代方案。 LocalAI 充当 REST API 的直接替代品&#xff0c;与本地推理的 OpenAI API 规范兼容。 它无需 GPU&#xff0c;还有多种用途集成&#xff0c;允许您使用消费级硬件在本地或本地运行 LLM、生成图像、音频等等&#…

spring boot(2.4.x 开始)和spring cloud项目中配置文件application和bootstrap加载顺序

在前面的文章基础上 https://blog.csdn.net/zlpzlpzyd/article/details/136060312 spring boot 2.4.x 版本之前通过 ConfigFileApplicationListener 加载配置 https://github.com/spring-projects/spring-boot/blob/v2.3.12.RELEASE/spring-boot-project/spring-boot/src/mai…

Apache 神禹(shenyu)源码阅读(一)——Admin向Gateway的数据同步(Admin端)

源码版本&#xff1a;2.6.1 单机源码启动项目 启动教程&#xff1a;社区新人开发者启动及开发防踩坑指南 源码阅读 前言 开了个新坑&#xff0c;也是第一次阅读大型项目源码&#xff0c;写文章记录。 在写文章前&#xff0c;已经跑了 Divide 插件体验了一下&#xff08;体…

Codeforces Round 113 (Div. 2)E. Tetrahedron(dp、递推)

文章目录 题面链接题意题解代码总结 题面 链接 E. Tetrahedron 题意 从一个顶点出发走过路径长度为n回到出发点的方案总数 题解 考虑dp f [ i ] [ 0 ∣ 1 ∣ 2 ∣ 3 ] f[i][0|1|2|3] f[i][0∣1∣2∣3]:走了i步&#xff0c;现在在j点的方案总数 转移&#xff1a; f [ i ]…

【Linux进程间通信】用管道实现简单的进程池、命名管道

【Linux进程间通信】用管道实现简单的进程池、命名管道 目录 【Linux进程间通信】用管道实现简单的进程池、命名管道为什么要实现进程池&#xff1f;代码实现命名管道创建一个命名管道 理解命名管道匿名管道与命名管道的区别命名管道的打开规则 作者&#xff1a;爱写代码的刚子…

【C语言进阶】深度剖析数据在内存中的存储--上

1. C语言中的数据类型的简单介绍 注&#xff1a;C99标准里面&#xff0c;定义了bool类型变量。这时&#xff0c;只要引入头文件stdbool.h &#xff0c;就能在C语言里面正常使用bool类型。 1.1 在C语言中各类型所占内存空间的大小如下 char类型的数据类型大小为1字节即8比特位。…

蓝桥杯每日一题------背包问题(三)

前言 之前求的是在特点情况下选择一些物品让其价值最大&#xff0c;这里求的是方案数以及具体的方案。 背包问题求方案数 既然要求方案数&#xff0c;那么就需要一个新的数组来记录方案数。动态规划步骤如下&#xff0c; 定义dp数组 第一步&#xff1a;缩小规模。考虑n个物品…

云原生容器化-4 Docker仓库

1.Docker仓库 1.1 Docker Hub docker仓库用于存放docker镜像&#xff0c;可以分为公用和私有两种。Docker Hub是全球公用的仓库&#xff0c;因服务器在国外&#xff0c;国内基本不可以&#xff1b;一般需要配置阿里、腾讯等加速器。公司内部而言&#xff0c;可以搭建私有的Do…

使用 devc++ 开发 easyx 实现 Direct2D 交互

代码为 codebus 另一先生的 文案 EasyX 的三种绘图抗锯齿方法 - CodeBus 这里移植到 devc 移植操作如下&#xff1a; 调用dev 的链接库方式&#xff1a; project -> project option -> 如图所示 稍作修改的代码。 #include <graphics.h> #include <d2d1.…

【数据结构】13:表达式转换(中缀表达式转成后缀表达式)

思想&#xff1a; 从头到尾依次读取中缀表达式里的每个对象&#xff0c;对不同对象按照不同的情况处理。 如果遇到空格&#xff0c;跳过如果遇到运算数字&#xff0c;直接输出如果遇到左括号&#xff0c;压栈如果遇到右括号&#xff0c;表示括号里的中缀表达式已经扫描完毕&a…