首页 > 其他分享 >基础代码-最小值维护

基础代码-最小值维护

时间:2022-11-22 18:35:19浏览次数:57  
标签:begin end 代码 len son 最小值 heap 维护 st


问题 A: 最小值维护

时间限制: 1 Sec  内存限制: 128 MB

题目描述


设计一个数据结构,支持以下两种操作:

1. 插入一个数

2. 输出并删除其中最小的数  

输入

输入文件的第一行为 n,代表操作的个数。
接下来有 n 行,每行包含一个操作,操作可能是以下两种格式:

1. ADD number,表示插入数字 “number”。
2. RELEASE MIN,表示输出当前数据结构中的最小值并将其删去。 

输出

对于每一个 RELEASE MIN 操作,如果当前数据结构内没有元素,输出 一行字符串"ERROR",否则输出一行一个整数,代表当前的最小值。  

样例输入

7
ADD 9
ADD 2
RELEASE MIN
ADD 1
RELEASE MIN
RELEASE MIN
RELEASE MIN

样例输出

2
1
9
ERROR

提示

对于所有数据,满足 n ≤ 200000, number 在 32 位有符号整形的表 示范围之内。 

二叉堆裸题……直接上模板。

Code:

var 
n,i,j,l,len:longint;st:ansistring;x:int64;
heap:array[0..205000]of int64;
procedure down(i:longint);
var son:longint;t:int64;
begin
while(i*2<=len)do
begin
son:=i*2;
if(i*2+1<=len)and(heap[i*2+1]<heap[i*2])then son:=i*2+1;
if(heap[son]>=heap[i])then break;
t:=heap[i];heap[i]:=heap[son];heap[son]:=t;
i:=son;
end;
end;
procedure push(x:int64);
var i:longint;t:int64;
begin
inc(len);
heap[len]:=x;
i:=len;
while i>0 do
begin
if(heap[i div 2]>heap[i])then
begin
t:=heap[i div 2];
heap[i div 2]:=heap[i];
heap[i]:=t;
end;
i:=i div 2;
end;
end;
begin
readln(n);
for i:=1 to n do
begin
readln(st);
if(st[1]='A')then
begin
l:=length(st);
for j:=5 to l do if st[j]<>' ' then break;
val(copy(st,j,l-j+1),x);
push(x);
end else
begin
if(len=0)then begin writeln('ERROR');continue;end;
writeln(heap[1]);
heap[1]:=heap[len];
dec(len);
down(1);
end;
end;
end.

标签:begin,end,代码,len,son,最小值,heap,维护,st
From: https://blog.51cto.com/u_15888102/5878320

相关文章

  • 基础代码-维护图的连通性
    问题D:维护图的连通性时间限制:1Sec  内存限制:128MB题目描述给定一个无向图G,写一个程序处理以下两种操作:1.删去一条边(u,v)......
  • 基础代码-维护集合
    问题C:维护集合时间限制:1Sec  内存限制:512MB题目描述维护一个字符串集合:初始为空,依次处理一些插入操作,并在插入之后输出该字符串在集合中出现的次数。......
  • 基础代码-计算后缀表达式
    问题E:计算后缀表达式时间限制:1Sec  内存限制:128MB题目描述后缀表达式是将运算符置于两个运算对象之后的一种表达方法,例如“3+4”用写成后缀表达式后就......
  • 基础代码-线段
    问题B:线段时间限制:1Sec  内存限制:128MB题目描述1.询问+LR增加一条线段[L,R],你的程序应该输出有多少条线段被该线段包含(非严格)。2.询问-L......
  • javascript-代码随想录训练营day6
    242.有效的字母异位词题目链接:https://leetcode.cn/problems/valid-anagram/题目描述:给定两个字符串s和t,编写一个函数来判断t是否是s的字母异位词。注意:若s......
  • 使用MSIL采用Emit方式实现C#的代码生成与注入常用代码
    本文主要使用微软提供的一套C#的API函数,通过这些API函数,可以对已经编译过的.Net体系生成的EXE,DLL文件进行修改,而不是修改源码编译的方式,来完成新功能的加入、或者原有功......
  • ECharts – 饼状图图代码实例及其注释详解
    mytextStyle={color:"#333",//文字颜色fontStyle:"normal",//italic斜体oblique倾斜fontWeight:"normal",//文字粗细boldbolderl......
  • ECharts – 折线图代码实例及注释
    mytextStyle={color:"#333",//文字颜色fontStyle:"normal",//italic斜体oblique倾斜fontWeight:"normal",//文字粗细boldbolderl......
  • ECharts – 柱形图代码实例及其注释详解
    mytextStyle={color:"#333",//文字颜色fontStyle:"normal",//italic斜体oblique倾斜fontWeight:"normal",//文字粗细boldbolderl......
  • Java实现网络爬虫 案例代码
    Java实现网络爬虫案例代码需求说明搭建开发环境,实现《三国演义》全文保存在本地 步骤分析访问网址:http://www.shicimingju.com/book/sanguoyanyi.html分析网站URL......