简答题
偏难
#7185
快速堆猪 小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是…
快速堆猪
小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。
时间限制: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>
这道题暂未补解析。