#2347. 「JOI 2018 Final」寒冬暖炉

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

JOI 的家里有一个暖炉。JOI 君比较耐寒,所以他独自在家里时不用开暖炉,但是有客人的时候就必须要开暖炉了。

这一天,JOI 有 N 个客人,第 i 位客人 (1≤i≤N) 到达的时间是时刻 T_i ,并在时刻 T_i+1 离开。不会有多位客人同时到访。

JOI 可以在任何时刻开启暖炉,不过在每次开启暖炉的时候会消耗一根火柴。JOI 只有 K 根火柴,所以最多只能开启暖炉 K 次。在这一天伊始,暖炉是关着的。

暖炉开着的时候需要燃料。为了节省燃料,JOI 想最小化暖炉工作的总时间。

给出 JOI 的客人们到访的时间以及 JOI 拥有的火柴根数,你需要编写一个程序计算暖炉最少需要工作多长时间。

输入格式

从标准输入中读取数据。

第一行包括两个整数 N, K ,表示有 N 位客人会拜访 JOI,并且 JOI 拥有 K 根火柴。

接下来 N 行,第 i+1 行给出一个整数 T_i ,表示第 i 位客人将在时刻 T_i 抵达,并且将在时刻 T_i+1 离开。

输出格式

输出数据到标准输出中。

输出一行一个整数,表示暖炉工作的最少时间是多少。

样例

样例输入 1
3 2
1
3
6
样例输出 1
4
样例说明 1

在这一天,有三位客人要拜访 JOI。按照下述方法开关暖炉,可以保证每位客人拜访的时候暖炉均是工作的。JOI 总共开启两次暖炉,并且暖炉总工作时间为 (4-1)+(7-6)=4

JOI 会在时刻 1 即第一位客人抵达的时候开启暖炉,并在时刻 4 即第二位客人离开的时候关闭暖炉。

JOI 会在时刻 6 即第三位客人抵达的时候开启暖炉,并在时刻 7 即第三位客人离开的时候关闭暖炉。

样例输入 2
3 1
1
2
6
样例输出 2
6
样例说明 2

在这个样例中,JOI 只能开启一次暖炉,因此他在第一位客人抵达的时候即时刻 1 开启暖炉,并在第三位客人离开的时候即时刻 7 关闭暖炉。

注意前一位客人离开的时候可以有另一位客人抵达。

样例输入 3
3 3
1
3
6
样例输出 3
3
样例说明 3

在这个样例中,JOI 可以在每次客人抵达的时候开启暖炉,并且在每次客人离开的时候关闭暖炉。

样例输入 4
10 5
1
2
5
6
8
11
13
15
16
20
样例输出 4
12

数据范围与提示

Subtask # 分值 N 其它
1 20 N\le 20 1 \le T_i \le 20(1 \le i \le N)
2 30 N \le 5000 -
3 50 N \le 10^5

对于所有输入数据,有 1≤N≤10^5 1≤K≤N 1≤T_i≤10^9 (1≤i≤N) T_i<T_{i+1} (1≤i≤N-1)