原题
解决思路
- 题目要求将所有元素通过 +- 的方式变成同一个元素 \(e\)，那么就需要找到一个点，计算小于（或大于）\(e\) 的所有点所需变化总次数
- 因此可以将二维数组转换成一维数组（总大小不变），并将其排序
- 通过计算前后缀和的方式计算出以任意一个 \(a_{ij}\) 为目标时，可能的最小值
#include <bits/stdc++.h>
int main() {
int n, m, d; std::cin >> n >> m >> d;
std::vector<int> arr(n * m + 2, 0);
int leader = 0;
bool ok = true;
for (int i = 1; i <= n * m; ++i) {
std::cin >> arr[i];
if (i == 1) leader = arr[i];
if (std::abs(leader - arr[i]) % d != 0) ok = false;
}
int ans = 0;
if (!ok) ans = -1;
else {
arr[n * m + 1] = 1e4 + 1;
std::sort(arr.begin() + 1, arr.end());
std::vector<int> smaller(n * m + 1, 0), larger(n * m + 2, 0);
for (int i = 1; i <= n * m; ++i) {
if (arr[i] > arr[i - 1]) {
int move = (arr[i] - arr[i - 1]) / d;
smaller[i] = smaller[i - 1] + (i - 1) * move;
} else {
smaller[i] = smaller[i - 1];
}
}
ans = 1e8 + 1;
for (int i = n * m; i >= 1; --i) {
if (arr[i] < arr[i + 1]) {
int move = (arr[i + 1] - arr[i]) / d;
larger[i] = larger[i + 1] + (n * m - i) * move;
} else {
larger[i] = larger[i + 1];
}
ans = std::min(ans, smaller[i] + larger[i]);
}
}
std::cout << ans << "\n";
return 0;
}