三校集训Part2 NBCX Day3 course 题解

题意

神秘男子的学校安排了$ N $门课,每门从时间$ start_i $上到时间$ end_i$。神秘男子一次只能上一门课。神秘男子想法很多,他想知道$ Q $个时间段$ planstart_j $到$ planend_j $内, 他分别最多上几节课。
对于$100\text{%}$的数据,$1\leq N,Q \leq 10^5,0\leq start_i,end_i,planstart_j,planend_j\leq 10^6$。

思路

对于30%的数据

贪心,将这$N$门课按照结束时间排序,课程能选则选。
预计得分:$30pts$
实际得分:$30pts$

对于60%的数据

对于每一个询问二分出第一节能选的课,预处理类似于链表的结构,处理出每节课结束以后的下一节课。时间复杂度:$O(\sum{ans[j]})$。
预计得分:$60pts$
实际得分:$60pts\text{~}90pts$

对于100%的数据

将算法$2$(即$60pts$)进行优化,构造出类似于森林的结构,倍增预处理一节课后$2^k$节课是什么,询问时想$LCA$处理。时间复杂度:$O(n \log n)$
预计得分:$100pts$
实际得分:$100pts$

Code

暂无评论

发送评论


				
上一篇
下一篇