首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#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 &lt;iostream&gt; using namespace std; typedef long long LL; int h[2005]; int size_; void up(int u){ while(u/2&amp;&amp;h[u/2]&gt;h[u]){ swap(h[u/2],h[u]); u/=2; } } void down(int u){ int t=u; if(u*2&lt;=size_&amp;&amp;h[u*2]&lt;h[u]) t=u*2; if(u*2+1&lt;=size_&amp;&amp;h[u*2+1]&lt;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&lt;&lt;h[1]&lt;&lt;endl; } else if(s=="push"){ cin&gt;&gt;n; size_++; h[size_]=n; up(size_); } } return 0; }</pre><p><br/></p>
这道题暂未补解析。