การดำเนินการน้อยที่สุดเพื่อทำให้ทุกองค์ประกอบในเมทริกซ์เท่ากันใน C++

ข้อกำหนดโจทย์

กำหนดจำนวนเต็ม K และเมทริกซ์ M x N งานคือหาจำนวนการดำเนินการน้อยที่สุดที่จำเป็นเพื่อทำให้ทุกองค์ประกอบของเมทริกซ์เท่ากัน ในหนึ่งการดำเนินการ K สามารถบวกหรือลบจากองค์ประกอบใดก็ได้ของเมทริกซ์

ตัวอย่าง

ถ้าอินพุตเมทริกซ์คือ: { {2, 4}, {20, 40} } และ K = 2 แล้วต้องการ 27 operations ดังนี้
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. เนื่องจากเราได้รับอนุญาตให้บวกหรือลบ K จากองค์ประกอบใดๆ เราสามารถสรุปได้ง่ายๆ ว่า mod ของทุกองค์ประกอบกับ K ควรเท่ากัน ถ้าไม่ใช่ คืนค่า -1
2. เรียงลำดับองค์ประกอบทั้งหมดของเมทริกซ์ในลำดับไม่ลดลง และหา median ขององค์ประกอบที่เรียงแล้ว
3. จำนวนขั้นตอนน้อยที่สุดจะเกิดขึ้นถ้าเราแปลงทุกองค์ประกอบให้เท่ากับ median

ตัวอย่างโค้ด 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 << "Minimum required operations = " << getMinOperations(n, m, k, matrix) << endl;
  return 0;
}

เมื่อคุณคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

Minimum required operations = 27