分数: 400 点
问题陈述
有 N 数轴上的布料。 的 i-th (1\le i\le N) 布覆盖间隔 \lbrack L _ i,R _ i\rbrack 上线了。 线上的一个点可能被两块或更多块布覆盖,或者没有任何一块布覆盖。
如果线上的某个点被两块布覆盖,则称两块布重叠。
对于两块不重叠的布料,定义它们的 距离 如下:
- 的最小值 |p-q| 超过所有点 p 用一块布覆盖所有点 q 被另一块布覆盖。
对于 K 没有两个重叠的布料,定义它们的 分数 本实验的 作为所有这些布料对之间的最小距离。 选择时求最大可能的分数 K 布料来自 N 布料,确保所选布料中没有两块重叠。
如果无法选择 K 这样的布,输出 -1.
约束
- 2\le K\le N\le2\times10 ^ 5
- 0\le L _ i\lt R _ i\le10 ^ 9\ (1\le i\le N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K L _ 1 R _ 1 L _ 2 R _ 2 \vdots L _ N R _ N
输出
输出答案。
示例输入 1
6 3 1 12 2 7 5 9 9 13 10 18 15 20
示例输出 1
2
选择第二块、第四块和第六块布,其中没有两块重叠。 第二块布和第四块布之间的距离为 2,第二块布和第六块布之间的距离为 8,第四块布和第六块布之间的距离为 2,所以这个选择的分数是 2.
不可能选择三件得分为 3 或更多,所以输出 2.
示例输入 2
2 2 1 5 5 9
示例输出 2
-1
给定的两块布料重叠,因此不可能选择两块布料使得没有两块重叠。
因此,输出 -1.
请注意,第一块布料和第二块布料仅在单个点处重叠 5.
示例输入 3
20 5 169 748 329 586 529 972 432 520 408 587 138 250 114 656 299 632 755 984 404 772 155 506 832 854 353 465 374 387 384 567 555 631 428 951 104 705 405 530 102 258
示例输出 3
35