Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom11月前

08/2
09:52
线段树

[bzoj 4653] [Noi2016]区间

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

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

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

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

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

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

2

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

把这些区间离散化后按照长度排序,看做一个队列,每次往线段树上加一段区间,当线段树上的某一个点覆盖数大于等于m时出队,从线段树上减去这个区间,同时记录答案

 

[bzoj 4653] [Noi2016]区间