分数: 533 分
问题陈述
高桥正在分析某只股票的股价数据 N 天。当日股价 i is H_i 日元。
Takahashi 希望将这些股价数据纠正为“每天严格增加”的理想数据集,以便包含在报告中。具体来说,他想要修正后的股价 H'_1, H'_2, \ldots, H'_N 满足 H'_1 < H'_2 < \cdots < H'_N.
通过单独更改每天的股价来进行修正。当日股价变动时 i 来自 H_i to H'_i,成本为 |H_i - H'_i|。高桥希望最大限度地减少全天变更的总成本, \sum_{i=1}^{N} |H_i - H'_i|.
然而,修正后的股价 每一天的 H'_i 必须是整数。
修正股票价格时求出最小总成本,使它们在所有日子里严格单调递增。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9
- 所有输入均为整数。
输入
N H_1 H_2 \cdots H_N
- 第一行包含一个整数 N 代表天数。
- 第二行包含 N 整数 H_1, H_2, \ldots, H_N 代表每天的股价,以空格分隔。
输出
在一行中打印最小总成本。
示例输入 1
5 5 3 2 4 5
示例输出 1
6
示例输入 2
7 3 3 3 3 3 3 3
示例输出 2
12
示例输入 3
10 10 1 12 3 14 5 16 7 18 9
示例输出 3
50