P7666 [JOI 2018 Final] 寒冬暖炉 / Stove

JOI 君的房间里有一个炉子。因为 JOI 君已经习惯了寒冷的温度，所以当他一个人在房间里时，他不需要打开炉子。但是，有客人时，他需要打开炉子。有一天，$N$ 位客人将拜访 JOI 君。第 $i$ 个客人 ($1 \leq i \leq N$) 将在时间 $T_i$ 到达，并在时间 $T_i+1$ 离开。任何时间最多有一个客人访问 JOI 君。JOI 君可以随时开火或关火。JOI 君用火柴打开炉子。JOI 君只有 $K$ 根火柴。 因此他最多可以打开炉子 $K$ 次。在一天的开始，炉子是关闭的。当炉子打开时，它需要燃料。因此，JOI 君控制着他何时打开或关闭炉子，他想尽量减少炉子的总运行时间。 现给定访问 JOI 君的客人数据和 JOI 君拥有的火柴数，请编写一个程序来计算炉子总运行时间的最小值。

第一行包含两个空格分隔的整数 $N$，$K$。 这意味着 $N$ 位客人将访问 JOI 君，而 JOI 君 有 $K$ 根火柴。接下来的下 $N$ 行的第 $i$ 行包含整数 $T_i$。这意味着第 $i$ 个客人将在时间 $T_i$ 到达，并在时间 $T_i+1$ 离开。

唯一的一行应包含一个整数为炉子总运行时间的最小值。

#### 数据规模与约定 对于 $100 \%$ 的数据，$1 \leq N \leq 10^5$，$1 \leq K \leq N$，$1 \leq T_i \leq 10^9$（$1 \leq i \leq N$），$T_i < T_{i+1}$（$1 \leq i \leq N-1$）。 - Subtask $1$（$20$ points）：$N \leq 20$。 - Subtask $2$（$30$ points）：$N \leq 5000$。 - Subtask $3$（$50$ points）：没有额外的限制。 #### 样例说明 **对于样例 $1$**：三位客人将访问 JOI 君。如果他按以下方式打开和关闭炉子，那么当客人来访时打开炉子，他打开炉子两次，炉子的总运行时间为 $(4-1)+(7-6)=4$。 - 当第一位客人到来时，他在时间 1 打开炉子。 - 当第二位客人离开时，他在时间 4 关掉炉子。 - 当第三位客人到来时，他在时间 6 打开炉子。 - 当第三位客人离开时，他在时间 7 关掉炉子。 由于炉子的总运行时间不能小于 $4$，输出 $4$。 **对于样例 $2$**：JOI 君只能打开一次炉子。因此，他在第一个客人来的时间 $1$ 打开炉子，当第三位客人离开时他在时间 $7$ 关掉炉子。 请注意，客人离开的时间可以与下一位客人到来的时间相同。 **对于样例 $3$**：JOI 君在每位客人到来时打开炉子，并在每位客人离开时关掉炉子。 #### 题目说明： 来源于 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round 的 [T1：Stove](https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho-t1-en.pdf)。 由 @[求学的企鹅](/user/271784) 翻译整理。