Skip to content

14274: 【原4274】憨憨移书

题目

题目描述

author: wrz 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4274

问题描述

铁憨憨的桌上有n摞书,这n摞书从左到右排成一排,依次编号为1,2,...,n。其中第$i$摞书由$a_i$本书组成。

铁憨憨觉得这n摞书看起来不美观,因此它决定对它们进行调整,使得最后这n摞书所包含的书的数量严格单调增加。严格单调增加是指,经过调整后,对于任意相邻的两摞书,左边这一摞书的数量一定小于右边这一摞书的数量。

铁憨憨每一秒都可以选定这n摞书中的一些,对于被选中的每一摞书,铁憨憨既可以在这摞书的顶部加一本书,也可以从这摞书的顶部移走一本书。

需要注意的是,任一时刻都要保证每一摞书至少还有一本。因为如果一摞书被全部移走了,铁憨憨会不开心。

例如,如果铁憨憨有5摞书,这五摞书所包含的书的数量分别为:2,3,3,3,3。

铁憨憨花费1秒时间,从第1,2摞书的顶部移去一本,这五摞书变为1,2,3,3,3 铁憨憨再花费1秒时间,在第3,5摞书的顶部加上一本书,这五摞书变为1,2,4,3,4 铁憨憨再花费1秒时间,在第4摞书的顶部加上一本书,这五摞书变为1,2,4,4,4 铁憨憨再花费1秒时间,在第4,5摞书的顶部加上一本书,并且从第3摞书的顶部移走一本书,这五摞书变为1,2,3,5,5 铁憨憨再花费1秒时间,在第5摞书的顶部加上一本书,并且从第4摞书的顶部移走一本书这五摞书变为1,2,3,4,6

这样,铁憨憨花费了5s的时间将这5摞书变成了严格单调增加的。但实际上对于这5摞书,金憨憨发现只需要花2秒的时间就可以把它们调整成严格单调增加的,过程如下:

金憨憨花费1秒时间,从第2摞书的顶部移走一本,并在第5摞书的顶部加上一本书,这五摞书变为2,2,3,3,4 金憨憨花费1秒时间,从第1摞书的顶部移走一本,并在第4,,5摞书的顶部加上一本书,这五摞书变为1,2,3,4,5

这样,金憨憨比铁憨憨少花了3秒就完成了调整,这3秒就可以用来续给有需要的人。

铁憨憨自闭了,因此他需要你的帮助。铁憨憨希望你能算出最少需要几秒,才能把n摞书调整成严格单调增加的。

输入格式

第 1 行一个整数 $n$,表示有 $n$ 摞书。 第二行有 $n$ 个正整数,对于第i个整数$a_i$,表示第 $i$ 摞书由 $a_i$ 本书组成。

输出格式

输出一行一个整数,表示把这 $n$ 摞书调整成严格单调增加所需要的最少秒数。

样例输入

5 2 3 3 3 3

样例输出

2

样例解释

详见题面。

数据规模

对于所有的数据,$n\le 50,a_i\le 10^9$。

本题由10个测试点组成,通过每一个测试点得到10分。部分测试点的特性如下:

|测试点|特性| |----|----| |1|$a_i$严格单调增加| |2~4|$n$摞书的书本数量完全相等,也就是对于任意两摞书$i$和$j$,$a_i=a_j$| |5~6|$a_i$严格单调减少| |7~8|$a_i\le 3000$| |9~10|无特性|

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!