校门内的树

校门内的树

题目描述
FZYZ 大门的左侧有一排 n 棵树木。它们按照距离的远近排列,第 1 棵树的高度为 a1 米,第 2 棵树木的高度为 a2 米,第 3 棵树木的高度为 a3 米,……,第 n 棵树木的高度为 an米。
为了给同学们以积极向上的感觉,一些同学自发地决定对树木进行修剪,使得树木呈现上升的趋势。具体地说,他们希望对树木进行修剪和整理,使得修剪之后的树木高度 b1,b2,b3,...,bn 米且满足 b1<b2<b3<...<bn。
他们不仅可以对较高的枝条进行修剪使其高度减小,还可以通过枝条的加固使得树木的高度增加,而且可以使树木的高度减小和增加任意的高度,但一定得是整数(单位为米),而且最后树的高度必须大于零。然而,树木的整理只能在课间进行,因此他们没有太多的时间。对于一棵树,将其修剪使其高度减少 x 米需要花费 x 分钟的时间,将其整理加固使其高度增加 x 米也需要花费 x 分钟的时间。
参加这次活动的同学超过 n 个,因此所有树木可以同时得到修剪或整理。请你帮他们求出,最少要花费多少的时间可以修剪使得树木递增。注意:花费的总时间取决于最后完成修剪或整理的同学。
输入格式
输入文件的第一行包含 1 个整数 n,表示树木的个数。
输入文件的第二行包含 n 个整数 a1,a2,a3,...,an,表示第 1 棵树的高度、第 2 棵树的高度、第 3 棵树的高度、……、第 n 棵树的高度。
输出格式
输出文件的第一行包含 1 个整数,表示能修剪使得树木具有“向上的趋势”的最短时间。
输入样例
【样例 1 输入】
3
9 5 11

【样例 2 输入】
2
5 8

【样例 3 输入】
5
1 1 1 1 1

【样例 4 输入】
5
548 47 58 250 2012
输出样例
【样例 1 输出】
3

【样例 2 输出】
0

【样例 3 输出】
4

【样例 4 输出】
251

样例说明
在样例 1 中,可以把第 1 棵树花费 2 分钟降低 2 米,第 2 棵树花费 3 分钟增加 3 米,总共花费 3 分钟,最终的高度分别为 7m,8m,11m;
在样例 2 中,原来的树就已经呈现了上升的趋势,因此不需要进行修剪或整理,所需要的时间为 0 分钟;
在样例 3 中,可以把第 2 棵树花费 1 分钟增加 1 米,第 3 棵树花费 2 分钟增加 2 米,第 4 棵树花费 3 分钟增加 3 米,第 5 棵树花费 4 分钟增加 4 米,总共花费 4 分钟,最终的高度分别为 1m,2m,3m,4m,5m。
数据规模与约定
对于 40% 的数据,n≤2;
对于 60% 的数据,n≤15;
对于 80% 的数据,ai≤3000;
对于 100% 的数据,n≤50,ai≤10^9。

信息

ID
1015
难度
9
分类
(无)
标签
递交数
8
已通过
1
通过率
12%
上传者