作者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://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1546505444.A.803.html
※ 编辑: nevikw39 (101.136.232.226), 01/03/2019 16:51:51
1F：→ yvb: 问题不是set没效率, 而是你内层for那段太没效率.01/03 20:20
2F：→ yvb: 当b值放大10倍, 你的内层for当然也做了10倍时间.01/03 20:22
3F：→ idiont: 当前作法改善的空间 就是直接用bool阵列取代set01/03 20:34
4F：→ idiont: 但是因为内层for太没效率 还是会TLE01/03 20:34
5F：→ idiont: 可以先排序每个线段 然後直接对区间做处理 而非每个点 01/03 20:37
感谢回答，果然是我想法不够缜密。另外请问如果要做 bool 阵列的话，应该用 vector 或
c-style 的较妥当？
※ 编辑: nevikw39 (106.107.176.158), 01/03/2019 21:34:08
6F：→ ilikekotomi: 比空间的话vector<bool>比bool阵列还好 01/03 21:44
7F：→ ilikekotomi: 但要先看一下说明因为vector<bool>比较特殊 01/03 21:45
8F：推 s06i06: 简化版的skyline algorithm 01/04 10:34
9F：推 s06i06: Nlog(N),N是input线段数 01/04 10:36