समस्या कथन
एक पूर्णांक 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 जोड़ने या घटाने की अनुमति है, हम आसानी से अनुमान लगा सकते हैं कि सभी तत्वों का K के साथ मॉड्यूलो बराबर होना चाहिए। यदि नहीं, तो -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 << "न्यूनतम आवश्यक ऑपरेशन = " << getMinOperations(n, m, k, matrix) << endl; return 0; }जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है
आउटपुट
न्यूनतम आवश्यक ऑपरेशन = 27
