[问题] 关于 set 的效率问题

楼主: nevikw39 (牧)   2019-01-04 00:50:41
如题,近来在高中生解题系统上练习 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 在插入的过程中,为
什么时间会落差如此之大?
作者: yvb   2019-01-04 04:20:00
问题不是set没效率, 而是你内层for那段太没效率.当b值放大10倍, 你的内层for当然也做了10倍时间.
作者: idiont (supertroller)   2019-01-04 04:34:00
当前作法改善的空间 就是直接用bool阵列取代set但是因为内层for太没效率 还是会TLE可以先排序每个线段 然后直接对区间做处理 而非每个点
作者: ilikekotomi (Young)   2019-01-04 05:44:00
比空间的话vector<bool>比bool阵列还好但要先看一下说明因为vector<bool>比较特殊
作者: s06i06 (三条鱼)   2019-01-04 18:34:00
简化版的skyline algorithmNlog(N),N是input线段数

Links booklink

Contact Us: admin [ a t ] ucptt.com