【在线编程产品介绍】

阿里云开发者社区在线编程：

免费刷题大神器，助你拿到好offer

周赛月赛不停歇，做题还能领奖品

大赛笔试全真题，常做常新有惊喜

点击链接开始产品体验：https://developer.aliyun.com/coding

本文为大家介绍的是“数组变换”的解法探究。先来看一下题目内容：

题目详情

等级：中等
知识点：排序、贪心
查看题目：数组变换

给出一个长度为 n 的数组，和一个正整数 d。你每次可以选择其中任意一个元素 a[i] 将其变为 a[i] + d 或 a[i] - d，这算作一次操作。

你需要将所有的元素全部变成相等元素，如果有解，请输出最小操作次数，如果无解请输出-1。
输入数字n、数字d，和一个长度为n的数组a。1 <= n <= 100000，1 <= d <= 100, 1 <= a[i] <= 100000。
输出一个数字，表示最小的操作次数，如果无解输出-1。
示例1
输入：
5
2
[3,5,7,1,9]
输出：
6
注意
最优解为全部变为5，共1 + 0 + 1 + 2 + 2 = 6次。

解题方法：

贡献者 | 猿圈

首先判断无解的情况，可以发现 a[i]，a[i]+d, a[i]-d 在 模d情况下的余数不会发生改变，因此如果原数组中的存在任意两个数字它们对d取余结果不同，那么此时无解。

设余数为r。判断完无解之后，需要求出最小值。

先将数组a[i]排序，然后除以d，得到从r变成a[i]需要的步数。

枚举元素a[i]，将所有元素全部变成a[i]需要考虑两部分，i之前和i之后:对于i之前的元素，假设都是r，那么需要 (i-1)*a[i]，但是因为并不都是0，所有我们可以用一个变量val存放前i-1项的和，然后我们在减去val就是前i-1个元素真正需要操作的步数。

对于i之后的元素，也是类似的。我们假设i之后的所有项和为val，假设我们要将它们变为r，则消耗即为val，但是我们只需要将其变为a[i]，因此需要减去(n-i)*a[i]。

看完之后是不是有了答题思路了呢，快来练练手吧：110.数组变换