codeforces 612 D. The Union of k-Segments

http://codeforces.com/contest/612/problem/D

题意:给出n个线段信息,每个线段以l,r的形式给出。给定k。要求从作到右给出至少有k个线段覆盖的区间的信息。并使得区间数目尽可能少。

思路:很经典的一类问题…又想起了当年在tyvj上海洋兄给我的那个把线段比喻成公路,把两个端点比喻成收费站的比喻了。做法是把所有点的信息按照从小到大排序,并且记录点的类型信息,如果点相同,那么我们规定入口处的优先级高。用pair来搞的话。。可以把入口的type规定成-1,出口规定成1.然后从最左边的点开始扫,遇到-1的点厚度+1,遇到1的点厚度-1.当厚度为k的时候记录区间信息。

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz