Acwing---839. 模拟堆

时间:2024-02-11 23:02:00 标签:  Acwing  

模拟堆

  • 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);}}}
}
来源:分享自作者个人站点/博客

智能推荐

模拟堆 1.题目2.基本思想3.代码实现 1.题目 维护一个集合&#xff0c;初始时集合为空&#xff0c;支持如下几种操作&#xff1a;

标签:Acwing  

  import java.io.*;public class Main{static int N &#61; 100010;static int[] h &#61; new int[N];static int size;public static void swap(int x,int y){int temp &#61; h[x];h[x] &#61; h[y];h[y] &#

标签:

[题目概述] X星球居民小区的楼房全是一样的&#xff0c;并且按矩阵样式排列。 其楼房的编号为 1,2,3… 当排满一行时&#xff0c;从下一行相邻的楼往反方向排号。 比如&#xff1a;当小区排号宽度为 6 时&#xff0c;开始情

标签:距离  

作者简介&#xff1a;大家好&#xff0c;我是smart哥&#xff0c;前中兴通讯、美团架构师&#xff0c;现某互联网公司CTO 联系qq&#xff1a;184480602&#xff0c;加我进群&#xff0c;大家一起学习&#xff0c;一起进步&#xff0c;一起对抗互联网寒冬 学习必须往深处挖&#xff0c;挖的越深&#xff0c;基础越扎实&#xff01; 阶段1、深入多线程阶段2、深入多线程设计模式阶段3、深入juc源码解析阶段4、深入jdk其余源码解析阶段5、深

标签:实战  

目录 关于堆的一些知识的回顾  数据结构&#xff1a;堆的特点

标签:数据结构  

题目1&#xff1a;连号区间数 题目链接&#xff1a;1210. 连号区间数 - AcWing题库 题意&#xff1a;题目给定一个区间&#xff0c;问有多少个子区间&#xff0c;满足在区间内的数字是连续的&#xff0c;比如像1,2,3就是连续的&#xff0c;1,2,4,就是断开的&#xff0c;从3这里断开。 思路&#xff1a; 暴力做法是枚举区间长度&#xff0c;查看区间是否满足要求&#xff0c;显然复杂度过大。 挖掘题目信息&#xff0c;发现题目给出的数字是一个排列&#xff0c;那么意味着数字不会重复&#xff0c;所以对于一段区间&#xff0c;只需要知道其最小值和最大值&

标签:辅导课  

输入一个长度为 n 的整数数列&#xff0c;从小到大

标签:模版  

[洛谷]P3378 【模板】堆方法一 手写堆最小堆插入从新增的最后一个结点的父结点开始,用要插入元素向下过滤上层结点(相当于要插入的元素向上渗透)void siftdown(int i) //传入一个需要向下调整的结点编号i,这里传入1,即从堆的顶点开始向下调整 { int t,flag=0;//flag用来标记是否需要继续向下调整 //当i结点有儿子的时候(其实是至少有左儿子的情况下)并且有需要继续调整的时候循环窒执行 while( i*2<

标签:模板  二叉堆  

一、理论 模型堆叠&#xff08;Model Stacking&#xff09;是一种集成学习的方法&#xff0c;其本质是将多个基学习器&#xff08;Individual Learner&#xff09;的预测结果作为新的特征&#xff0c;再训练一个元学习器&#xff08;Meta Learner&#xff09;来进行最终的预测。每个基学习器可以使用不同的算法或参数来训练&#xff0c;因此理论上你可以将任何可以输出概率值的模型作为基学习器进行模型堆叠。

标签:模型  

题解借鉴两位大佬的解析 墨染空 && 野生铅笔本题是一道 01背包 的扩展题 —— 二维费用01背包问题把 野生宝可梦 看做物品,则捕捉他需要的 精灵球 个数就是第一费用,战斗皮神要掉的血就是第二费用在背包问题中,体积w与价值v是可以互逆的!可以将f[i]表示为体积为i能装的最大价值,也可以将f[i]表示为价值为i所需的最小体积。以上就是本题的

标签:Acwing  

heapq模块 heapify(list)建立小根堆heappush(heap, item)推入元素到堆中heappop(heap)从堆中弹出元素heapreplace(heap,item)弹出

标签:模块  

差分 1.题目2.基本思想3.代码实现 1.题目 输入一个长度为

标签:差分  

  import java.util.Scanner;public class Main{public static void m

标签:

输入样例&#xff1a; 10push 6emptyquerypopemptypush 3push 4popquerypush 6 输出样例&#xff1a; NO6YES4 import java.util.Sca

标签:队列  

1.简单模拟输入和输出测试          1.打开项目&#xff0c;在FPGA终端下面新建一个VI         2.本示例以模拟输入卡和模拟输出卡同时举例。         3.新建一个VI编写程序&#xff0c;同时将卡1的输出连接到卡2的输入使用物理连线。         4.编译并运行程序&#xff0c;观察是否能从通道中采集和输出信号。

标签:入门  

phpCurl函数类,网上很多,这里分享一个万能phpcurl,包含phpcurl函数类模拟Curl get post header refer携带Cookie模拟访问来源Refer模拟UseaAgent<?php/** * @author 教书先生 * @link https://blog.oioweb.cn * @date 2021年6月13日10:29:04 * @msg PHPCurl封

标签:函数  来源  post  cURL  phpcurl  

算法分析棋盘型状态压缩dp这类dp有一个通用的状态表示法:f[i][j][k],表示前i行(放了j个棋子后)的状态表示为k。由于本题无棋子要求,因此可以省去中间一维,即:  用f[i][j]表示前i行土地的状态为j。首先由于玉米地有不肥沃的地方不能种植,因此需要通过二进制表示出来可以种植和不可以种植的地方,我们是将整行用一个二进制数表示的,可种为0,不可种为1,在输入的时候即可判断:  g[i] += (!x<<(j-1)) //g[i]为每一行土地的二进制表示由于是棋盘型,因此根据我们的

标签:玉米田  Acwing  

单链表 1.题目2.基本思想3.代码实现 1.题目 实现一个单链表&#xff0c;链表初始为空&#xff0c;支持三种操作&#xff1a;

标签:链表  

区间和 1.题目2.基本思想3.代码实现 1.题目 假定有一个无限长的数轴&#xff0c;数轴上每个坐标上的数都是 0。 现在&#xff0c

标签:区间  

写在前面近期的学习重点要放在图论了,之前一直在acwing中学习的数据结构都是数组模拟,数组模拟的效率比上stl要快上几倍,学完过后不久就会忘记,但是忘记也是一种学习,原本准备放弃数组模拟直接上stl要轻松的多,可是图论又得用到大量的数组模拟,最后还是打算攻坚克难把数组模拟各种数据结构给啃下来。(除此之外还能用来装*ヾ(•ω•`)o)数组模拟(一)目录写在前面数组模拟(一)单链表双链表模拟栈模拟队列单链表

标签:数组  

Step1 安装chrome的这个插件 St

标签:Elasticsearch  

1. 什么是堆、大顶堆和小顶堆堆是一种非线性结构,可以把堆看作一棵二叉树,也可以看作一个数组,即:堆就是利用完全二叉树的结构来维护的一维数组。堆可以分为大顶堆和小顶堆:大顶堆:每个结点的值都大于或等于其左右孩子结点的值。小顶堆:每个结点的值都小于或等于其左右孩子结点的值。用简单的公式来描述一下堆的定义就是:大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]小顶堆:arr[i]

标签:大顶堆  小顶堆  

模拟算法 基本思想引入算法题替换所有的问号提莫攻击Z字形变换外观数列数青蛙

标签:算法  

猜你喜欢

一、介绍1.1 物理含义雪花是人们最常见的枝晶。枝晶生长是一种生长的不稳定现象,常起因于过冷的液体,或晶体的生长速度受限于溶质原子向固体表面的扩散速度。造成以上条件的原因,可以是液相中负的温度梯度,也可以是负的浓度梯度。在这种模式下,晶体倾向于在其棱角处优先生长,从而形成突触状结构。这篇博文会介绍用相场模拟的方法,模拟雪花生长的过程。1.2 相场模拟介绍在相场法中,使用连续变量描述微观结构特征。这些变量有两种形式:代表物理性质的守恒变量,如原子浓度或材料密度;描述材料微观结构(包括晶粒和不同相)的非守恒序参数(order parameters)。这些连续变量的演化用自由能的函数表达,可以定义为一

标签:雪花  生长  COMSOL  

1. 预期效果当数据变动时,触发自定义的回调函数。2. 思路对对象 object 的 setter 进行设置,使 setter 在赋值之后执行回调函数 callback()。3.细节3.1 设置 setter 和 getterJS提供了 [Object.defineProperty()](Object.defineProperty() - JavaScript

标签:原理  数据  vue  

目录 一、队列的概念 二、队列的接口

标签:数据结构  

一、SYN Flood原理 在TCP三次握手过程中&#xff0c; 客户端发送一个SYN包给服务器服务端接收到SYN包后&#xff0c;会回复SYN&#43;ACK包给客户端&#xff0c;然后等待客户端回复ACK包。但此时客户端并不会回复ACK包&#xff0c;所以服务端就只能一直等待直到超时。服务端超时后会重发SYN&#43;ACK包给客户端&#xff0c;默认会重试5次&#xff0c;而且每次等待的时间都会增加。 服务器收到客户端发来的SYN会建立一个半连接状态的Socket&#xff0c;当客户端在一定时间内持续不断的发大量的SYN包但不回复ACK包&#xff0c;就会

标签:协议  

统一大小写按题意1.统计大小写字母个数2.按照要求转换为小写或大写,输出#include<cstdio>#include<cstring>#include<iostream>using namespace std;bool check(char c){//判断大小写 if(c>=a && c<=z) return 1; else return 0;}string s;int t;int main(){ cin>>t; while(t--){ ci

标签:Acwing  场周赛  

url:4366. 上课睡觉 - AcWing题库题意:给n个石堆,相邻石堆可以合并现在要求每个石堆都相等,问最少合并多少次思路:由于不管咋个合并,石子数是不会变的那么就可以枚举一下合并成多少个石堆然后再用石子总数 / 目标石堆数,就为每堆石堆的石子数这时候就会发现,有的石堆数是无法合并成的因为石堆数必须为石子总数的质因子不然石堆数 * 每堆的石子数 != 石子总数了然后就是如何去判断合成x堆石堆是否合法这里我就没想到咋个去判断其实不用管咋

标签:Acwing  

url:4645. 选数异或 - AcWing题库题意:给n个数,再给m次查询,给一个数x每次询问给一个区间l,r,问是否能从$[l,r]$中选出两个下标不同的数使得它们的异或值等于x思路:这题有个异或性质我没想到(找两个数使得$a[l] ⊕ a[r] = x$根据异或的交换性来说式子可以变成:$a[r] ⊕ x = a[l]$那么我们直接用$a[r] ⊕ x$即可得到$a[l]$这时候问题就变成了去找离r最近的$a[r] ⊕ x$即可暴力思路就是先枚举后端点,往前枚举前端点,记录每个点的

标签:Acwing  选数异  

思路&#xff1a;我们按照从小到大的顺序将数组逆转好&#xff0c;然后枚举数组首项&#xff0c;分别让其&#43;1&#xff0c;-1&#xff0c;&#43;0&#xff0c;然后求出公差&#xff0c;从前往后遍历即可。 代码&#xff1a; int ans1(){//不动int cha &#61; (a[n] - a[1] &#43;

标签:Acwing  

差分矩阵 1.题目2.基本思想3.代码实现 1.题目 输入一个

标签:矩阵  

A题 签到模拟即可 B题 单独考虑每一个a[i]&#xff0c;如果i要是答案需要指针移动多少次&#xff0c;然后算完&#xff0c;排个序&#xff0c;指针移动最少的就是答案。

标签:Acwing  

合并集合 1.题目2.基本思想3.代码实现 1.题目 一共有

标签:Acwing  

只模拟的话直接终端运行会快很多 计数器举例 mkdir src counter.v

标签:终端  

只模拟的话直接终端运行会快很多 计数器举例 mkdir src counter.v

标签:终端  

C&#43;&#43; vector模拟实现 一.我们要实现的大致框架1.STL库中是如何实现的呢?1.迭代器2.成员变量3.vector的特性

标签:VECTOR  

2024.1.20 模拟赛总结 总结时间安排考试结果考试总结 题解T1T2

标签:

目录 TPM模拟器安装 1&#xff09;安装配置所需依赖

标签:模拟器  

在学习过程种 &#xff0c;学习看源码是很有必要的&#xff0c;它可以让你更清楚的知道一些代码的细节&#xff0c;你也会发现源码将效率利用到了极致&#xff0c;不得不佩服写出源码的人。 下面我将配合源码来实现一个简单的vector&#xff0c;下面请看源码 看源码我们首先要看的就是成员变量&#xff0c;我们可以看到源码中有迭代器的start、finish、end_of_storage三个成员变量

标签:STL  

 环境配置 1:打开CMD nvidia-smi.exe   查询显卡

标签:声音  

目录 一、成员变量 二、迭代器 2.1 正向迭代器

标签:VECTOR  

模拟类题目是机试题中出现频率很高的一种类型&#xff0c;这类题目的特点是并不涉及特别高 深的知识&#xff0c;只需利用程序实现题目的要求。由于这类题目通常不需要经过太多的思考&#xff0c;所以能够很纯粹地考查考生的编程能力。 1. 图形排版

标签:

目录 一、改造红黑树 1、模板T改造节点

标签:mapset