分数: 366 分
问题陈述
高桥在采石场工作。有 N 岩石在采石场排成一排,他需要将它们全部摧毁。
的 i第岩石具有硬度 H_i。高桥按照从上至下的顺序将岩石一颗一颗地加工 1-st 摇滚到 N第岩石。在当前岩石被摧毁之前,他无法继续处理下一块岩石。
每回合,高桥选择并执行以下两个动作之一:
- 用锤子敲击:降低当前正在加工的岩石的硬度 1。这消耗 1 转。
- 使用炸药:立即降低当前正在加工的岩石的硬度 0。这消耗 1 转。然而,高桥只有 K 炸药棒,每次使用消耗 1 坚持。当他有以下动作时,不能选择该动作 剩余的 0 棒。
当岩石的硬度变为 0,该岩石被破坏,他继续处理下一块岩石。一旦所有岩石都被摧毁,工作就完成了。
求当高桥表现最佳时摧毁所有岩石所需的最少回合数。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq N
- 1 \leq H_i \leq 10^9
- 所有输入均为整数
输入
N K H_1 H_2 \ldots H_N
- 第一行包含一个整数 N 代表岩石的数量和一个整数 K 代表炸药棒的数量,以空格分隔。
- 第二行包含整数 H_1, H_2, \ldots, H_N 代表每块岩石的硬度,以空格分隔。
输出
打印摧毁一行中所有岩石所需的最小圈数。
示例输入 1
3 1 5 2 8
示例输出 1
8
示例输入 2
5 2 10 3 7 4 6
示例输出 2
15
示例输入 3
8 3 100 5 200 8 150 3 50 300
示例输出 3
169