P1712 [NOI2016]区间

题目描述

在数轴上有 n个闭区间 [l1,r1],[l2,r2],…,[ln,rn]。现在要从中选出 m 个区间,使得这 m个区间共同包含至少一个位置。换句话说,就是使得存在一个 x,使得对于每一个被选中的区间 [li,ri],都有 li≤x≤ri。

对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li,即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案,输出 −1。

emm…不用关心哪个点被覆盖了M次,只关心整个序列有没有存在这么一个点,那么我们可以想把区间按照长度排序,从最小开始加起,每次找到一组合法解之后,按顺序减去先前短的区间,判断是不是可行解,

如果是的话,去掉那个区间一定比现在的优。这样操作可以理解为

找到一组解之后尝试逼近最优解

然后记录最小值就行了。

但是数据范围巨大,所以要离散化不过我离散化写的丑..

 


说点什么

avatar
  Subscribe  
提醒