[问题] priority_queue与min-heap

楼主: engine210 (Steven)   2019-06-05 20:57:01
问题(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;
}
作者: cutekid (可爱小孩子)   2019-06-05 21:33:00
-2147483648 ?
作者: Sylveon (仙子精靈)   2019-06-05 22:28:00
TA 的测资有 -2147483648 欧XD经确认 2/5 侧资有非预期的内容,会在更正后重新rejudge
楼主: engine210 (Steven)   2019-06-06 00:14:00
欧欧欧所以是测资有其他问题吗xd,想说long long 应该就不会有溢位的问题了可是还是过不了
作者: Lipraxde (Lipraxde)   2019-06-06 01:43:00
如果啊,用 -(k+1),是不是就不用担心溢位了?
作者: RishYang (Rish)   2019-06-06 07:47:00
用long long 应该要可以AC
作者: cutekid (可爱小孩子)   2019-06-06 12:37:00
推 Lipraxde →-(k+1)
楼主: engine210 (Steven)   2019-06-06 15:23:00
-(k+1)试过了也不行qq
作者: LPH66 (-6.2598534e+18f)   2019-06-06 23:09:00
不要写成 -(k+1) 这样会先加 1 再负还是一样用 ~k 就可以了, 这个是 bitwise not不过这其实不是正常写法, 还是明确指定比较函数比较好
作者: xavier13540 (柊 四千)   2019-06-07 01:30:00
猜测你只有把容器的int改成long long -x本身还是int当x=INT_MIN时 -x=INT_MIN 容器装long long也没用
作者: Fenikso (薪水小偷)   2019-06-07 02:10:00
测资有问题.. 那原po用min-heap是怎么过的 XD
作者: RishYang (Rish)   2019-06-07 08:35:00
@xavier13540我测过这个问题,很神秘的还是会错
作者: kevin4314 (LauZi)   2019-06-07 17:59:00
感觉是测资爆int

Links booklink

Contact Us: admin [ a t ] ucptt.com