[問題] 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