bzoj 3888: [Usaco2015 Jan]Stampede STL+扫描线

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=3888


先算出每个牛(羊驼)所覆盖的时间段,之后的操作都是对于时间段上的操作。

不好的习惯:查题解。查完发现都是线段树…

我又突然想起我之前做的题,都是区间覆盖,然后找最上面的(这个题

每个区间拆成两个端点,然后按照时间从小到大排个序

每次把时间相同的点全都处理掉,这个过程用可删堆,关于y的小根堆,实现方法是一个优先队列和一个set,插入就往队列里插入,删除就往set里插入,求堆顶时,如果当前堆顶在set中发现了,那么就pop掉,直到堆空了或者堆顶在set中没找到

然后在每次之后把堆顶的id标记一下,因为我们一定能看到它

最后1~n扫一遍就好了

 

发表评论