题目描述

塔子哥拿到了一个数组，他每次操作可以任选一个元素加1或者减1。他想知道，将所有元素都变成和$a_i$相等需要操作最少多少次?你需要回答$i ∈[1,n]$的结果，

题目思路

最优的操作其实就是让小于它的数一直自增直到其等于指定元素，大于它的数一直自减直到其等于指定元素。

所以对每个元素我们需要找到大于它的元素数量和元素之和，小于它的元素数量和元素之和就可以计算出答案。

可以增加一个排序后的镜像的数组，对每个元素找到其在排序后的镜像数组的下标位置,这个可以通过二分找到，也就找到了小于它的元素数量和大于它的元素数量。元素之和则考虑使用前缀和优化即可。

代码