问题(Question):
题目输入有三种指令
PUSH k //把k加到heap
POP //删除heap中的最小值
TOP //输出heap中的最小值
我直接使用
priority_queue<int, vector<int>, greater<int>>
可以AC
但是如过我仍然使用
priority_queue<int>,
也就是max heap
然后在push资料时push -k进去,
pop时再打印出负值,
逻辑上应该也可以达到min-heap的效果,
但是有两笔测资一直过不了,
就算换成long long也是一样,
想请问是哪里有bug,谢谢大家!
这是这题的oj网址
https://acm.cs.nthu.edu.tw/problem/12316/
程式码(Code):(请善用置底文网页, 记得排版,禁止使用图档)
这是有两笔测资过不了的程式码
http://codepad.org/VvfpJVDk
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main(int argc, const char * argv[]) {
priority_queue<long long> q;
string cmd;
long long num;
while (cin >> cmd) {
if (cmd == "PUSH") {
cin >> num;
q.push(-num);
}
else if (cmd == "POP" && !q.empty()) {
q.pop();
}
else if (cmd == "TOP"){
if (q.empty()) {
cout << "Null" << endl;
}
else {
cout << -q.top() << endl;
}
}
}
return 0;
}