作者engine210 (香菇菜鸡汤)
看板C_and_CPP
标题[问题] priority_queue与min-heap
时间Wed Jun 5 20:57:01 2019
问题(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;
}
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.114.222.158 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1559739424.A.53D.html
1F：推 cutekid: -2147483648 ? 06/05 21:33
2F：推 Sylveon: TA 的测资有 -2147483648 欧XD 06/05 22:28
3F：推 Sylveon: 经确认 2/5 侧资有非预期的内容，会在更正後重新rejudge 06/05 23:04
4F：→ engine210: 欧欧欧所以是测资有其他问题吗xd，想说long long 应该 06/06 00:14
5F：→ engine210: 就不会有溢位的问题了可是还是过不了 06/06 00:14
6F：→ Lipraxde: 如果啊，用 -(k+1)，是不是就不用担心溢位了？ 06/06 01:43
7F：→ RishYang: 用long long 应该要可以AC 06/06 07:47
8F：推 cutekid: 推 Lipraxde →-(k+1) 06/06 12:37
9F：→ engine210: -(k+1)试过了也不行qq 06/06 15:23
10F：推 LPH66: 不要写成 -(k+1) 这样会先加 1 再负还是一样 06/06 23:09
11F：→ LPH66: 用 ~k 就可以了, 这个是 bitwise not 06/06 23:09
12F：→ LPH66: 不过这其实不是正常写法, 还是明确指定比较函数比较好 06/06 23:10
13F：推 xavier13540: 猜测你只有把容器的int改成long long -x本身还是int 06/07 01:30
14F：→ xavier13540: 当x=INT_MIN时 -x=INT_MIN 容器装long long也没用 06/07 01:33
15F：推 Fenikso: 测资有问题.. 那原po用min-heap是怎麽过的 XD 06/07 02:10
16F：→ RishYang: @xavier13540我测过这个问题，很神秘的还是会错 06/07 08:35
17F：→ kevin4314: 感觉是测资爆int 06/07 17:59