Số phép toán tối thiểu làm tất cả phần tử ma trận bằng nhau trong C++

Đề bài

Cho số nguyên K và ma trận M x N, nhiệm vụ là tìm số phép toán tối thiểu để làm cho tất cả phần tử ma trận bằng nhau. Trong một phép toán, K có thể được cộng vào hoặc trừ từ bất kỳ phần tử nào của ma trận.

Ví dụ

Nếu ma trận đầu vào:
{ 
    {2, 4},
    {20, 40}
}
và K = 2 thì cần 27 phép toán như sau:
Matrix[0][0] = 2 + (K * 9) = 20 = 9 phép toán
Matrix[0][1] = 4 + (K * 8) = 20 = 8 phép toán
Matrix[1][0] = 20 + (K * 10) = 40 = 10 phép toán

Thuật toán

1. Vì chỉ được phép cộng hoặc trừ K từ bất kỳ phần tử nào, dễ suy ra modulo của tất cả phần tử với K phải bằng nhau. Nếu không, trả về -1.
2. Sắp xếp tất cả phần tử ma trận theo thứ tự không giảm và tìm trung vị của các phần tử đã sắp xếp.
3. Số bước tối thiểu xảy ra khi chuyển tất cả phần tử bằng trung vị.

Ví dụ mã C++

#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 << "Số phép toán tối thiểu = " << getMinOperations(n, m, k, matrix) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Số phép toán tối thiểu = 27