A4549 | dloonc
来源官方 / 2024
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Ytiroirp的房间里有一个炉子。
因为 Ytiroirp 已经习惯了寒冷，所以当他一个人在房间里时，他不需要打开炉子。
但是，有客人时，他需要打开炉子。有一天，$n$ 位客人将拜访Ytiroirp。第 $i$ 个客人 ($1 \leq i \leq n$) 将在时间 $T_i$ 到达，并在时间 $T_i+1$ 离开。任何时刻至多有一个客人访问Ytiroirp。
Ytiroirp 可以随时命令 Elbisivid 去开火或关火。但是命令次数多了，Elbisivid 就会鄙视他，所以 Ytiroirp 只有 $k$ 次命令的机会。 因此他最多可以打开炉子 $k$ 次。在一天的开始，炉子是关闭的。
当炉子打开时，它需要燃料。因此，Ytiroirp控制着他何时打开或关闭炉子，他想尽量减少炉子的总运行时间。
现 $n,k$ 和每个客人的到达时间，求炉子总运行时间的最小值。
因为 Ytiroirp 已经习惯了寒冷，所以当他一个人在房间里时，他不需要打开炉子。
但是，有客人时，他需要打开炉子。有一天，$n$ 位客人将拜访Ytiroirp。第 $i$ 个客人 ($1 \leq i \leq n$) 将在时间 $T_i$ 到达，并在时间 $T_i+1$ 离开。任何时刻至多有一个客人访问Ytiroirp。
Ytiroirp 可以随时命令 Elbisivid 去开火或关火。但是命令次数多了，Elbisivid 就会鄙视他，所以 Ytiroirp 只有 $k$ 次命令的机会。 因此他最多可以打开炉子 $k$ 次。在一天的开始，炉子是关闭的。
当炉子打开时，它需要燃料。因此，Ytiroirp控制着他何时打开或关闭炉子，他想尽量减少炉子的总运行时间。
现 $n,k$ 和每个客人的到达时间，求炉子总运行时间的最小值。
输入格式
第 $1$ 行两个整数，分别表示 $n,k$。
第 $2\sim n+1$ 行，每行一个整数，第 $i$ 行的整数表示 $T_{i-1}$。
第 $2\sim n+1$ 行，每行一个整数，第 $i$ 行的整数表示 $T_{i-1}$。
输出格式
输出一个整数，表示答案。
输入输出样例
输入 #1
3 2 1 3 6
输出 #1
4
输入 #2
10 5 1 2 5 6 8 11 13 15 16 20
输出 #2
12
输入 #3
6 3 1 11 114 1145 11451 114514
输出 #3
1147
对于 $40\%$ 的数据，$k\le n \le 20$。
对于 $70\%$ 的数据，$k\le n \le 5000$。
对于 $100\%$ 的数据，$k\le n \le 10^5,1\le T_i\le 10^9,T_i<T_{i+1}(1\le i<n)$。
对于 $70\%$ 的数据，$k\le n \le 5000$。
对于 $100\%$ 的数据，$k\le n \le 10^5,1\le T_i\le 10^9,T_i<T_{i+1}(1\le i<n)$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？