C++에서 행렬의 모든 요소를 ​​동일하게 만들기 위한 주어진 유형의 최소 연산

문제 설명

정수 K와 M x N 행렬이 주어졌을 때 작업은 행렬의 모든 요소를 ​​동일하게 만드는 데 필요한 최소 연산 수를 찾는 것입니다. 단일 연산으로 행렬의 모든 요소에 K를 더하거나 뺄 수 있습니다.

예시

If input matrix is:
{
   {2, 4},
   {20, 40}
} and K = 2 then total 27 operations required as follows;
Matrix[0][0] = 2 + (K * 9) = 20 = 9 operations
Matrix[0][1] = 4 + (k * 8) = 20 = 8 operations
Matrix[1][0] = 20 + (k * 10) = 40 = 10 operations

알고리즘

1. Since we are only allowed to add or subtract K from any element, we can easily infer that mod of all the elements with K should be equal. If it’s not, then return -1
2. sort all the elements of the matrix in non-deceasing order and find the median of the sorted elements
3. The minimum number of steps would occur if we convert all the elements equal to the median

예시

#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