3733 - 小b浇花
描述

小b养了 n 盆花,第 i 盆花高度为 A[i]。

小b每天可以给某一盆花浇水,这样这盆花就会长高一单位。

小b希望每盆花都是独一无二的,也就是不存在两盆花高度相等。

求小b最少要浇几天水。

输入

第一行输入一个非负整数 n;
第二行输入 n 个非负整数,表示 A[i];
其中 0 <= n <= 40000,0 <= A[i] < 40000。

输出

输出一个非负整数,表示答案。

样例

输入

6
3 2 1 2 1 7

输出

6
提示

把花按高度从小到大排序,从左到右依次处理:若当前花高度不超过前一盆,就把它浇到“前一盆高度 + 1”。由于排序后只需单向前进,这样得到的就是最少总浇水天数,复杂度 O(n log n)。

来源
51nod 2519
标签
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 1
通过次数 1