给定一个大小为平方的矩阵 
.查找所需的最小操作数，以使每行和每列上的元素之和相等。在一次操作中，将矩阵单元的任意值增加1。在第一行中，打印所需的最小运算量，在接下来的“n”行中，打印代表运算后最终矩阵的“n”整数。 例子：
null
Input: 1 23 4Output: 44 33 4Explanation1. Increment value of cell(0, 0) by 32. Increment value of cell(0, 1) by 1Hence total 4 operation are requiredInput: 91 2 34 2 33 2 1Output: 62 4 3 4 2 3 3 3 3
方法很简单，假设 maxSum 是所有行和列中的最大和。我们只需要增加一些单元格，使任何行或列的和变成“maxSum”。 比方说 十、 我 是使行“i”上的和等于所需的操作总数 maxSum 和 Y J 是使列“j”上的和等于 maxSum .从X开始 我 =Y J 所以我们需要根据情况对其中任何一个进行操作。 为了尽量减少 十、 我 ，我们需要从中选择最大值 罗森 我 和 科尔苏姆 J 因为它肯定会导致最小的操作。之后，根据递增后满足的条件递增“i”或“j”。 以下是上述方法的实施情况。
C++
/* 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 << "" ; } } // Driver code int main() { int matrix[][2] = { { 1, 2 }, { 3, 4 } }; cout << findMinOpeartion(matrix, 2) << "" ; printMatrix(matrix, 2); return 0; } |
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#
// 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. |
Javascript
<script> // Javascript 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 function findMinOpeartion(matrix,n) { // Initialize the sumRow[] // and sumCol[] array to 0 let sumRow = new Array(n); let sumCol = new Array(n); for (let i=0;i<n;i++) { sumRow[i]=0; sumCol[i]=0; } // Calculate sumRow[] and // sumCol[] array for (let i = 0; i < n; ++i) for (let 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 let maxSum = 0; for (let i = 0; i < n; ++i) { maxSum = Math.max(maxSum, sumRow[i]); maxSum = Math.max(maxSum, sumCol[i]); } let count = 0; for (let i = 0, j = 0; i < n && j < n;) { // Find minimum increment // required in either row // or column let 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 function printMatrix(matrix,n) { for (let i = 0; i < n; ++i) { for (let j = 0; j < n; ++j) document.write(matrix[i][j] + " " ); document.write( "<br>" ); } } /* Driver program */ let matrix=[[1, 2],[3, 4]]; document.write(findMinOpeartion(matrix, 2)+ "<br>" ); printMatrix(matrix, 2); // This code is contributed by avanitrachhadiya2155 </script> |
Output44 33 4
时间复杂性： O（n） 2. ) 辅助空间： O（n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
