首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#7352

快速堆猪 小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是…

快速堆猪

小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。

时间限制: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>
这道题暂未补解析。