作者nevikw39 (牧)
看板C_and_CPP
標題[問題] 關於 set 的效率問題
時間Thu Jan 3 16:50:41 2019
如題,近來在高中生解題系統上練習 apcs 的題目。目前正卡關於 b966 線段覆蓋長度。
https://zerojudge.tw/ShowProblem?problemid=b966
現在的狀況是 na score 70%,前兩筆測資分別 11 , 10 ms,最後一組測資 tle 。據此,
我推論問題應該在乎效率的部分。
https://pastebin.com/n5YqVnR7
我的想法是讀入各端點後將範圍內的點都放入 set 中,再計算 set 內元素總個數。
進一步測試,發現當 a = 1, b = 999999 可以在 1 秒內算出,但當 b = 9999999 時竟
然要花到 6 秒。
因此,請教各位,根據這個做法,有沒有改善的空間?unordered_set 在插入的過程中,為
什麼時間會落差如此之大?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.136.232.226
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1546505444.A.803.html
※ 編輯: nevikw39 (101.136.232.226), 01/03/2019 16:51:51
→ yvb: 問題不是set沒效率, 而是你內層for那段太沒效率.01/03 20:20
→ yvb: 當b值放大10倍, 你的內層for當然也做了10倍時間.01/03 20:22
→ idiont: 當前作法改善的空間 就是直接用bool陣列取代set01/03 20:34
→ idiont: 但是因為內層for太沒效率 還是會TLE01/03 20:34
→ idiont: 可以先排序每個線段 然後直接對區間做處理 而非每個點 01/03 20:37
感謝回答,果然是我想法不夠縝密。另外請問如果要做 bool 陣列的話,應該用 vector 或
c-style 的較妥當?
※ 編輯: nevikw39 (106.107.176.158), 01/03/2019 21:34:08
→ ilikekotomi: 比空間的話vector<bool>比bool陣列還好 01/03 21:44
→ ilikekotomi: 但要先看一下說明因為vector<bool>比較特殊 01/03 21:45
推 s06i06: 簡化版的skyline algorithm 01/04 10:34
推 s06i06: Nlog(N),N是input線段數 01/04 10:36