问题 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标签:begin,end,代码,len,son,最小值,heap,维护,st From: https://blog.51cto.com/u_15888102/5878320
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.