C++ 中，求使矩阵所有元素相等的给定类型的最少运算次数
c++server side programmingprogramming
问题描述
给定一个整数 K 和一个 M x N 的矩阵，任务是求使矩阵所有元素相等所需的最少运算次数。在一次运算中，K 可以添加到矩阵的任何元素上或从矩阵的任何元素中减去。
示例
如果输入矩阵为:
{
{2, 4},
{20, 40}
} 且 K = 2，则总共需要 27 次运算，如下所示:
Matrix[0][0] = 2 + (K * 9) = 20 = 9 次运算
Matrix[0][1] = 4 + (k * 8) = 20 = 8 次运算
Matrix[1][0] = 20 + (k * 10) = 40 = 10 次运算
算法
1. 由于我们只能对任意元素加或减 K，因此我们可以很容易地推断，所有元素的 mod 值都应该相等。如果不相等，则返回 -1 2. 对矩阵的所有元素进行非降序排序，并找到排序后元素的中位数 3. 如果将所有元素转换为等于中位数的数，则步骤数最少
示例
#include <bits/stdc++.h>
using namespace std;
int getMinOperations(int n, int m, int k, vector<vector<int> >& matrix) {
vector<int> arr(n * m, 0);
int mod = matrix[0][0] % k;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
arr[i * m + j] = matrix[i][j];
if (matrix[i][j] % k != mod) {
return -1;
}
}
}
sort(arr.begin(), arr.end());
int median = arr[(n * m) / 2];
int minOperations = 0;
for (int i = 0; i < n * m; ++i)
minOperations += abs(arr[i] - median) / k;
if ((n * m) % 2 == 0) {
int newMedian = arr[(n * m) / 2];
int newMinOperations = 0;
for (int i = 0; i < n * m; ++i)
newMinOperations += abs(arr[i] - newMedian) / k;
minOperations = min(minOperations, newMinOperations);
}
return minOperations;
}
int main() {
vector<vector<int> > matrix = {
{ 2, 4},
{ 20, 40},
};
int n = matrix.size();
int m = matrix[0].size();
int k = 2;
cout << "Minimum required operations = " <<
getMinOperations(n, m, k, matrix) << endl;
return 0;
}
编译并执行上述程序，将生成以下输出
输出
Minimum required operations = 27
