简答题
偏难
#7423
快速堆猪(2023.9) 小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在…
快速堆猪(2023.9)
小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。
时间限制:1000
内存限制:65536
输入
有三种输入 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
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre><p><br/></p>
这道题暂未补解析。