P1712 [NOI2016]区间

    • 315通过
    • 918提交
  • 题目提供者kkksc03 站长团
  • 标签 排序 离散化 线段树 NOI系列 2016 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 1s-3s / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

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

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

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

    输入输出格式

    输入格式:

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

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

    N<=500000,M<=200000,0≤li≤ri≤10^9

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    6 3
    3 5
    1 2
    3 4
    2 2
    1 5
    1 4
    输出样例#1: 复制
    2

    说明

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。