A38151. 快速堆猪
填空题
困难
知识点
题目描述
快速堆猪
题目描述
小明有很多猪，他喜欢玩叠猪游戏，就是将猪一头头叠起来。猪叠上去后，还可以把顶上的猪拿下来。小明知道每头猪的重量，而且他还随时想知道叠在那里的猪最轻的是多少斤。
输入
有三种输入1)push n n是整数(0<=0 <=20000)，表示叠上一头重量是n斤的新猪 2)pop 表示将猪堆顶的猪赶走。如果猪堆没猪，就啥也不干 3)min 表示问现在猪堆里最轻的猪多重。如果猪堆没猪，就啥也不干 输入总数不超过100000条
输出
对每个min输入，输出答案。如果猪堆没猪，就啥也不干
样例输入
pop
min
push 5
push 2
push 3
min
push 4
min
样例输出
2
2
参考答案
#include <iostream>
using namespace std;
typedef long long LL;
int h[2005];
int size_;
void up(int u) {
while(u/2&&h[u/2]>h[u]) {
swap(h[u/2],h[u]);
u/=2;
}
}
void down(int u) {
int t=u;
if(u*2<=size_&&h[u*2]<h[u]) t=u*2;
if(u*2+1<=size_&&h[u*2+1]<h[u]) t=u*2+1;
if(u!=t) {
swap(h[u],h[t]);
down(t);
}
}
int main() {
char t[10];
string s;
int n;
while(scanf("%s",t)!=EOF) {
s=string(t);
if(s=="pop") {
if(size_==0) continue;
h[1]=h[size_];
size_--;
down(1);
} else if(s=="min") {
if(size_==0) continue;
cout<<h[1]<<endl;
} else if(s=="push") {
cin>>n;
size_++;
h[size_]=n;
up(size_);
}
}
return 0;
}
上一题
下一题