小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)。