# 使矩陣的每一行和每一列相等所需的最少操作 > 原文： [https://www.geeksforgeeks.org/minimum-operations-required-make-row-column-matrix-equals/](https://www.geeksforgeeks.org/minimum-operations-required-make-row-column-matrix-equals/) 給定大小為的方陣。 查找所需的最小操作數，以使每一行和每一列上的元素總數相等。 在一個操作中，將矩陣單元格的任何值加 1。在第一行中，打印所需的最小操作，在接下來的“ n”行中，打印“ n”個整數，表示操作后的最終矩陣。 **例如**： ``` Input: 1 2 3 4 Output: 4 4 3 3 4 Explanation 1\. Increment value of cell(0, 0) by 3 2\. Increment value of cell(0, 1) by 1 Hence total 4 operation are required Input: 9 1 2 3 4 2 3 3 2 1 Output: 6 2 4 3 4 2 3 3 3 3 ``` 方法很簡單，假設 **maxSum** 是所有行和列中的最大和。 我們只需要增加一些單元格，以使任何行或列的總和變為“ maxSum”。 假設 **X _i** 是使行“ i”上的總和等于 **maxSum** 和 **Y [ _j** 是使列'j'的總和等于 **maxSum** 所需的操作總數。 由于 X _i = Y _j ，因此我們需要根據條件對其中任何一個進行操作。 為了最小化 **X _i** ，我們需要從 **rowSum _i** 和 **colSum _{j [}** ，因為它肯定會導致最低限度的運行。 之后，根據遞增后滿足的條件遞增“ i”或“ j”。 下面是上述方法的實現。 ## C++ ```cpp /* C++ Program to Find minimum number of operation required such that sum of elements on each row and column becomes same*/ #include <bits/stdc++.h> using namespace std; // Function to find minimum operation required // to make sum of each row and column equals int findMinOpeartion(int matrix[][2], int n) { ????// Initialize the sumRow[] and sumCol[] ????// array to 0 ????int sumRow[n], sumCol[n]; ????memset(sumRow, 0, sizeof(sumRow)); ????memset(sumCol, 0, sizeof(sumCol)); ????// Calculate sumRow[] and sumCol[] array ????for (int i = 0; i < n; ++i) ????????for (int j = 0; j < n; ++j) { ????????????sumRow[i] += matrix[i][j]; ????????????sumCol[j] += matrix[i][j]; ????????} ????// Find maximum sum value in either ????// row or in column ????int maxSum = 0; ????for (int i = 0; i < n; ++i) { ????????maxSum = max(maxSum, sumRow[i]); ????????maxSum = max(maxSum, sumCol[i]); ????} ????int count = 0; ????for (int i = 0, j = 0; i < n && j < n;) { ????????// Find minimum increment required in ????????// either row or column ????????int diff = min(maxSum - sumRow[i], ???????????????????????maxSum - sumCol[j]); ????????// Add difference in corresponding cell, ????????// sumRow[] and sumCol[] array ????????matrix[i][j] += diff; ????????sumRow[i] += diff; ????????sumCol[j] += diff; ????????// Update the count variable ????????count += diff; ????????// If ith row satisfied, increment ith ????????// value for next iteration ????????if (sumRow[i] == maxSum) ????????????++i; ????????// If jth column satisfied, increment ????????// jth value for next iteration ????????if (sumCol[j] == maxSum) ????????????++j; ????} ????return count; } // Utility function to print matrix void printMatrix(int matrix[][2], int n) { ????for (int i = 0; i < n; ++i) { ????????for (int j = 0; j < n; ++j) ????????????cout << matrix[i][j] << " "; ????????cout << "\n"; ????} } // Driver code int main() { ????int matrix[][2] = { { 1, 2 }, ????????????????????????{ 3, 4 } }; ????cout << findMinOpeartion(matrix, 2) << "\n"; ????printMatrix(matrix, 2); ????return 0; } ``` ## Java ```java // Java Program to Find minimum? // number of operation required? // such that sum of elements on? // each row and column becomes same import java.io.*; class GFG { ????// Function to find minimum ????// operation required ????// to make sum of each row ????// and column equals ????static int findMinOpeartion(int matrix[][], ?????????????????????????????????????????int n) ????{ ????????// Initialize the sumRow[] ????????// and sumCol[] array to 0 ????????int[] sumRow = new int[n]; ????????int[] sumCol = new int[n]; ????????// Calculate sumRow[] and ????????// sumCol[] array ????????for (int i = 0; i < n; ++i) ????????????for (int j = 0; j < n; ++j) ????????????{ ????????????????sumRow[i] += matrix[i][j]; ????????????????sumCol[j] += matrix[i][j]; ????????????} ????????// Find maximum sum value? ????????// in either row or in column ????????int maxSum = 0; ????????for (int i = 0; i < n; ++i)? ????????{ ????????????maxSum = Math.max(maxSum, sumRow[i]); ????????????maxSum = Math.max(maxSum, sumCol[i]); ????????} ????????int count = 0; ????????for (int i = 0, j = 0; i < n && j < n;)? ????????{ ????????????// Find minimum increment ????????????// required in either row ????????????// or column ????????????int diff = Math.min(maxSum - sumRow[i], ????????????????????????maxSum - sumCol[j]); ????????????// Add difference in? ????????????// corresponding cell, ????????????// sumRow[] and sumCol[] ????????????// array ????????????matrix[i][j] += diff; ????????????sumRow[i] += diff; ????????????sumCol[j] += diff; ????????????// Update the count? ????????????// variable ????????????count += diff; ????????????// If ith row satisfied, ????????????// increment ith value? ????????????// for next iteration ????????????if (sumRow[i] == maxSum) ????????????????++i; ????????????// If jth column satisfied,? ????????????// increment jth value for ????????????// next iteration ????????????if (sumCol[j] == maxSum) ????????????????++j; ????????} ????????return count; ????} ????// Utility function to? ????// print matrix ????static void printMatrix(int matrix[][], ?????????????????????????????????????int n) ????{ ????????for (int i = 0; i < n; ++i)? ????????{ ????????????for (int j = 0; j < n; ++j) ????????????????System.out.print(matrix[i][j] + ???????????????????????????????????????????" "); ????????????System.out.println(); ????????} ????} ????/* Driver program */ ????public static void main(String[] args) ????{ ????????int matrix[][] = {{1, 2}, ??????????????????????????{3, 4}}; ????????System.out.println(findMinOpeartion(matrix, 2)); ????????printMatrix(matrix, 2); ????} } // This code is contributed by Gitanjali.? ``` ## Python 3 ``` # Python 3 Program to Find minimum? # number of operation required such? # that sum of elements on each row # and column becomes same? # Function to find minimum operation? # required to make sum of each row? # and column equals def findMinOpeartion(matrix, n): ????# Initialize the sumRow[] and sumCol[] ????# array to 0 ????sumRow = [0] * n ????sumCol = [0] * n ????# Calculate sumRow[] and sumCol[] array ????for i in range(n): ????????for j in range(n) : ????????????sumRow[i] += matrix[i][j] ????????????sumCol[j] += matrix[i][j] ????# Find maximum sum value in? ????# either row or in column ????maxSum = 0 ????for i in range(n) : ????????maxSum = max(maxSum, sumRow[i]) ????????maxSum = max(maxSum, sumCol[i]) ????count = 0 ????i = 0 ????j = 0 ????while i < n and j < n : ????????# Find minimum increment required? ????????# in either row or column ????????diff = min(maxSum - sumRow[i],? ???????????????????maxSum - sumCol[j]) ????????# Add difference in corresponding? ????????# cell, sumRow[] and sumCol[] array ????????matrix[i][j] += diff ????????sumRow[i] += diff ????????sumCol[j] += diff ????????# Update the count variable ????????count += diff ????????# If ith row satisfied, increment? ????????# ith value for next iteration ????????if (sumRow[i] == maxSum): ????????????i += 1 ????????# If jth column satisfied, increment ????????# jth value for next iteration ????????if (sumCol[j] == maxSum): ????????????j += 1 ????return count # Utility function to print matrix def printMatrix(matrix, n): ????for i in range(n) : ????????for j in range(n): ????????????print(matrix[i][j], end = " ") ????????print() # Driver code if __name__ == "__main__": ????matrix = [[ 1, 2 ], ??????????????[ 3, 4 ]] ????print(findMinOpeartion(matrix, 2)) ????printMatrix(matrix, 2) # This code is contributed # by ChitraNayal ``` ## C# ```cs // C# Program to Find minimum? // number of operation required? // such that sum of elements on? // each row and column becomes same using System; class GFG { ????// Function to find minimum ????// operation required ????// to make sum of each row ????// and column equals ????static int findMinOpeartion(int [,]matrix, ????????????????????????????????????????int n) ????{ ????????// Initialize the sumRow[] ????????// and sumCol[] array to 0 ????????int[] sumRow = new int[n]; ????????int[] sumCol = new int[n]; ????????// Calculate sumRow[] and ????????// sumCol[] array ????????for (int i = 0; i < n; ++i) ????????????for (int j = 0; j < n; ++j) ????????????{ ????????????????sumRow[i] += matrix[i,j]; ????????????????sumCol[j] += matrix[i,j]; ????????????} ????????// Find maximum sum value? ????????// in either row or in column ????????int maxSum = 0; ????????for (int i = 0; i < n; ++i)? ????????{ ????????????maxSum = Math.Max(maxSum, sumRow[i]); ????????????maxSum = Math.Max(maxSum, sumCol[i]); ????????} ????????int count = 0; ????????for (int i = 0, j = 0; i < n && j < n;)? ????????{ ????????????// Find minimum increment ????????????// required in either row ????????????// or column ????????????int diff = Math.Min(maxSum - sumRow[i], ????????????????????????maxSum - sumCol[j]); ????????????// Add difference in? ????????????// corresponding cell, ????????????// sumRow[] and sumCol[] ????????????// array ????????????matrix[i,j] += diff; ????????????sumRow[i] += diff; ????????????sumCol[j] += diff; ????????????// Update the count? ????????????// variable ????????????count += diff; ????????????// If ith row satisfied, ????????????// increment ith value? ????????????// for next iteration ????????????if (sumRow[i] == maxSum) ????????????????++i; ????????????// If jth column satisfied,? ????????????// increment jth value for ????????????// next iteration ????????????if (sumCol[j] == maxSum) ????????????????++j; ????????} ????????return count; ????} ????// Utility function to? ????// print matrix ????static void printMatrix(int [,]matrix, ????????????????????????????????????int n) ????{ ????????for (int i = 0; i < n; ++i)? ????????{ ????????????for (int j = 0; j < n; ++j) ????????????????Console.Write(matrix[i,j] + ????????????????????????????????????????" "); ????????????Console.WriteLine(); ????????} ????} ????/* Driver program */ ????public static void Main() ????{ ????????int [,]matrix = {{1, 2}, ????????????????????????{3, 4}}; ????????Console.WriteLine(findMinOpeartion(matrix, 2)); ????????printMatrix(matrix, 2); ????} } // This code is contributed by Vt_m.? ``` ``` Output 4 4 3 3 4 ``` **時間復雜度**： `O(n^2)` **輔助空間**：`O(n)` * * * * * *