← 返回题目列表

AtCoder · utpc2013_07

G. 暑假期间保洁值班

中文机器翻译题面 查看原题

問題

背景

鳗鱼王国的学生们总是在学校地下的学生活动室中学习。学生活动室由于总是有学生在,所以平时打扫得很干净,但到了暑假学生不来学校时,学生活动室就会布满灰尘。因此学生们决定即使在暑假期间也来学校打扫学生活动室。然而学生们能来学校的日子有限,并且不太想来学校。于是暂时决定让每个学生都打扫一次,但这还不够,所以需要让部分学生每天都来学校。如何分配才能保持学生活动室的整洁呢?

課題

当将清洁工作分配给学生,使得最长未清洁的时间最短时,请回答该时间为多少天。

学生人数 N暑假的天数 M参数 K 。 i 第几位学生 ai 减去 bi 只能在……期间来学校。此外,每个学生只能被安排清洁一次。但是 K 可以随便选择……名学生,并让这些学生在他们能来学校的期间每天都来学校帮忙清洁。

配点

200

入力

输入按以下格式给出。

N M K
a1 b1
...
aN bN

N 是学生人数,M 是暑假的天数,K 是每天来学校的学生人数,ai,bi 是 您也可以写 i 表示第几位学生能够来学校的期间。

制約

输入中的每个变量都满足以下约束。

  • 1 \leq N \leq 105
  • 1 \leq M \leq 109
  • 0 \leq K \leq N
  • 1 \leq ai \leq bi \leq M

部分点

针对此问题设置了部分分数。这个问题的测试用例50这些点还满足以下约束。

  • K=0

出力

问题的解决办法 在1行输出。 没有

入力例1

1 2 0
1 2

输入示例 1 的输出示例 路径

2

1第……天当值时也会2第……天当值时最长间隔会是2天。

図 1

入力例2

1 2 1
1 2

输入示例 2 的输出示例

1

因为可以每天来学校,所以最长的间隔是1天。

図 2

入力例3

2 6 1
2 2
4 5

输入示例 3 的输出示例

2
図 3