解题思路

把所有数变成某个目标 $x$ 的代价是 $\sum |a_j-x|$ 。对每个原来的 $a_i$ 都要求这个值。

将数组排序并做前缀和后，对任意 $x$ 可用二分定位，在 $O(\log n)$ 内算出小于 $x$ 与大于 $x$ 两部分的代价。

复杂度分析

时间复杂度 $O(n \log n)$ ，空间复杂度 $O(n)$ 。

产线侧对一批测点做了抽检，得到长度为 $n$ 的正整数读数。质检规程允许对任意一个测点做一次微调：把它的读数加 1 或减 1，每次计一次操作。为了让整条样本带落到同一校准档，需要把所有读数都改成与某个已有测点 $a_i$ 完全相同。

请对每个下标 $i$ ，求出以 $a_i$ 作为目标档时的最少操作次数。

约束：测点个数不超过 100000，每个读数为正整数且不超过 1000000000。