← 返回题目列表

AtCoder · awc0005_c

C. 楼梯形花坛

中文机器翻译题面 查看原题

分数: 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