A7168 | $雾港学宫的时钟塔调度$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

雾港学宫的时钟塔每天都会敲响 $n$ 次钟声，用来提示不同的课程与仪式。第 $i$ 次钟声原本被记录在整数时刻 $a_i$（你可以把它理解为“第几分钟”或“第几个刻度”）。 但负责抄写的学徒有些粗心，导致记录中可能出现同一时刻被写了多次，甚至后面的钟声比前面的还早。为了不让全校的安排混乱，学宫规定：修正后必须满足 $$ a_1<a_2<\cdots<a_n, $$ 也就是钟声时刻严格递增。 你只有一种修正手段：每次可以选择一个位置 $i$（$1\le i\le n$），把这一项的时刻往后挪一点点： $$ a_i := a_i + 1. $$ 你可以进行任意多次修正。请你计算：最少需要多少次修正，才能让所有钟声时刻严格递增。

第一行一个整数 $n$。 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$

输出一个整数，表示最少操作次数。

输入 #1

5
3 3 2 2 10

输出 #1

测试点编号$n$ 上界$a_i$ 范围$1 \sim 4$$n \le 20$$\|a_i\| \le2 \times 10^{9}$$5 \sim 10$$n \le 10000$$\|a_i\| \le2 \times 10^{9}$$11 \sim 20$$n \le 200000$$\|a_i\| \le2 \times 10^{9}$

C++ 编辑器

输入

输出