作者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://www.ptt.cc/bbs/C_and_CPP/M.1559739424.A.53D.html
推 cutekid: -2147483648 ? 06/05 21:33
推 Sylveon: TA 的測資有 -2147483648 歐XD 06/05 22:28
推 Sylveon: 經確認 2/5 側資有非預期的內容,會在更正後重新rejudge 06/05 23:04
→ engine210: 歐歐歐所以是測資有其他問題嗎xd,想說long long 應該 06/06 00:14
→ engine210: 就不會有溢位的問題了可是還是過不了 06/06 00:14
→ Lipraxde: 如果啊,用 -(k+1),是不是就不用擔心溢位了? 06/06 01:43
→ RishYang: 用long long 應該要可以AC 06/06 07:47
推 cutekid: 推 Lipraxde →-(k+1) 06/06 12:37
→ engine210: -(k+1)試過了也不行qq 06/06 15:23
推 LPH66: 不要寫成 -(k+1) 這樣會先加 1 再負還是一樣 06/06 23:09
→ LPH66: 用 ~k 就可以了, 這個是 bitwise not 06/06 23:09
→ LPH66: 不過這其實不是正常寫法, 還是明確指定比較函數比較好 06/06 23:10
推 xavier13540: 猜測你只有把容器的int改成long long -x本身還是int 06/07 01:30
→ xavier13540: 當x=INT_MIN時 -x=INT_MIN 容器裝long long也沒用 06/07 01:33
推 Fenikso: 測資有問題.. 那原po用min-heap是怎麼過的 XD 06/07 02:10
→ RishYang: @xavier13540我測過這個問題,很神秘的還是會錯 06/07 08:35
→ kevin4314: 感覺是測資爆int 06/07 17:59