[BZOJ4653/Luogu1712][NOI2016]区间(线段树,尺取法)

发布于 2018-04-17  5 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4653/Luogu1712][NOI2016]区间(线段树,尺取法)

Description

在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间,使得这 m个区间共同包含至少一个位置。换句话说,就是使得存在一个 x,使得对于每一个被选中的区间 [li,ri],都有 li≤x≤ri。
对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li,即等于它的右端点的值减去左端点的值。
求所有合法方案中最小的花费。如果不存在合法的方案,输出 −1。

Tag

线段树,尺取法。

解决思路

由于题目定义方案的花费为最长区间的长度-最短区间长度,那么长度在两者之间的区间是都可以加进去的。所以如果爱把区间按照长度排序后,任意一个合法方案都是一段连续区间的组合。
那么,可以用尺取法维护这个合法区间。每一次加入一个区间,就在对应线段树节点进行区间加法操作,若全局max等于要求的m时,此时表示至少有一个位置被m个区间覆盖,记录答案,然后移动左端点去掉一个区间,继续做。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4653/Luogu1712][NOI2016]区间(线段树,尺取法)


HNCJ OIer 一枚