[codeforces754D] Fedor and coupons

题目大意

N个线段,从中选k个线段,使得交集最大。

题解

官方提供的解法是,二分答案,然后每个线段都减去mid,由于被更新后的线段的交集可以延展mid,所以问题就转化为是否存在k条线段有交集,这个可以利用线段树来解决,因此总的时间复杂度为O(n\log n\log R),比较慢。

另外一种解法是,我们按照l升序排列,那么我们很容易发现,最终答案的左端点,一定是某条线段的左端点。于是我们只需要在这个基础上寻找最大化最小的r值即可,但是问题在于是否会出现不存在交集的情况,我们不必担心,因为我们已经按照l升序了,那么出现不存在交集的条件只可能是l_{j}>r_{i},\;\;(j<i),可以推出r_{j}>r_{i},那就不会影响我们的答案,因为我们堆中始终维护的都是最小的r值。时间复杂度O(n\log n)

代码

http://codeforces.com/contest/754/submission/23726733

发表评论