[問題] 關於 set 的效率問題
如題，近來在高中生解題系統上練習 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
→
01/03 20:20,
7年前
, 1F
01/03 20:20, 1F
→
01/03 20:22,
7年前
, 2F
01/03 20:22, 2F
→
01/03 20:34,
7年前
, 3F
01/03 20:34, 3F
→
01/03 20:34,
7年前
, 4F
01/03 20:34, 4F
→
01/03 20:37,
7年前
, 5F
01/03 20:37, 5F
感謝回答，果然是我想法不夠縝密。另外請問如果要做 bool 陣列的話，應該用 vector 或
c-style 的較妥當？
※ 編輯: nevikw39 (106.107.176.158), 01/03/2019 21:34:08
→
01/03 21:44,
7年前
, 6F
01/03 21:44, 6F
→
01/03 21:45,
7年前
, 7F
01/03 21:45, 7F
推
01/04 10:34,
7年前
, 8F
01/04 10:34, 8F
推
01/04 10:36,
7年前
, 9F
01/04 10:36, 9F
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
