AC. 梦想

frank_c1

[NOI 2016] 区间

发布于2016年08月07日 | 暂无评论 | 545阅读 | 线段树

题目描述

在数轴上有n个闭区间[l_1,r_1],[l_2,r_2],...,[l_n,r_n]。现在要从中选出m个区间,使得这m个区间共同包含至少一个位置。换句话说,就是使得存在一个x,使得对于每一个被选中的区间[l_i,r_i],都有l_i \le x \le r_i

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

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

输入格式

第一行包含两个正整数n,m,用空格隔开,意义如上文所述。保证1 \le m \le n

接下来n行,每行表示一个区间,包含用空格隔开的两个整数l_ir_i为该区间的左右端点。

1 \le n \le 5 \cdot 10 ^ 5, 1 \le m \le 2 \cdot 10 ^ 5

输出格式

只有一行,包含一个正整数,即最小花费。

题目解析

有个简单的转化。如果我们用若干线段覆盖数轴,满足其中至少有一个点被覆盖了不少于m次,我们就一定能从这些线段中选出m条作为一种方案。这是一个求全局最大值的问题。

根据这个结论,有一种双指针的做法。我们维护当前选取线段的最短长度和最长长度l,r,线段树维护所有长度在[l,r]中的线段的覆盖,r递增,l需要满足当前全局最大值不小于m的同时最大。

于是我们把线段按长度排序,扫描一遍即可,扫描过程中统计答案。

时间复杂度O(n \log n)