分数: 333 分
问题陈述
高桥是一名园丁,负责维护一排花坛。
有 N 花坛,每个编号从 1 to N。每个花坛 i (1 \leq i \leq N) 目前有 A_i 里面种着花。
据高桥老板介绍,这排花坛要处于美丽状态的条件是“对于所有相邻的花坛来说,花朵数量的绝对差最多为 K。”换句话说,如果我们表示每个花坛中的花朵数量 i 维护后为 B_i,那么这排花坛被认为是美丽的,当 |B_i - B_{i+1}| \leq K 适用于所有人 i (1 \leq i \leq N - 1).
高桥可以种植新花,但不能移除已经种植的花。具体来说,对于每个花坛 i,他可以添加 0 或更多鲜花以增加鲜花数量 A_i to B_i。在这里,每一个 B_i 必须是满足以下条件的整数 B_i \geq A_i.
高桥希望尽量减少添加的鲜花总数 \displaystyle\sum_{i=1}^{N} (B_i - A_i) 为了让这排花坛变得漂亮。找到这个最小值。
请注意,仅通过添加花朵总是可以实现美丽的状态,因为可以通过设置所有来满足条件 B_i 到相同的足够大的值。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
- 所有输入均为整数
输入
N K A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表花坛数量和一个整数 K 表示相邻花坛之间允许的花朵数量差异,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个花坛当前种植的花朵数量 i,用空格分隔。
输出
在一行中输出使这排花坛变得漂亮需要添加的最少花朵总数。
示例输入 1
3 2 1 5 3
示例输出 1
2
示例输入 2
5 3 2 4 5 3 1
示例输出 2
0
示例输入 3
7 10 5 30 15 50 20 100 85
示例输出 3
235