看板 C_and_CPP 關於我們 聯絡資訊
問題(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