Por que esse algoritmo sempre funciona? Operações mínimas necessárias para tornar cada linha e coluna da matriz igual a - algoritmo

Dada uma matriz quadrada de tamanho n x n. O número mínimo de operações é necessário para que a soma dos elementos em cada linha e coluna se torne igual. Em uma operação, incremente qualquer valor de célula de matriz em 1. Na operação mínima de impressão de primeira linha necessária e nas próximas linhas 'n' imprima números inteiros representando a matriz final após a operação.

Entrada:

1 2
3 4

Saída:

4
4 3
3 4

Explicação

1. Valor de incremento da célula (0, 0) por 3
2. Valor de incremento da célula (0, 1) por 1 Portanto, total de 4 operações são necessárias

Entrada: 9

1 2 3
4 2 3
3 2 1

Saída:

6
2 4 3
4 2 3
3 3 3

Explicação da solução:

A abordagem é simples, vamos supor que maxSumé a soma máxima entre todas as linhas e colunas. Precisamos apenas incrementar algumas células de modo que a soma de qualquer linha ou coluna se torne "maxSum". Digamos que Xi é o número total de operações necessárias para que a soma na linha "i" seja igual a maxSum e Yj seja o número total de operações necessárias para que a soma na coluna "j" seja igual a maxSum. Como Xi = Yj, precisamos trabalhar em qualquer um deles de acordo com a condição.

Para minimizar o Xi, precisamos escolher omáximo de rowSumi e colSumj, pois certamente levará a operação mínima. Depois disso, incremente "i" ou "j" de acordo com a condição satisfeita após o incremento.

Abaixo está a implementação da abordagem acima.

Código da Solução:

// 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.

Minha pergunta:

Eu não entendo porque este código funciona com todoscasos. Não é óbvio para mim, por que para resolver o problema eu posso apenas começar do canto superior esquerdo da matriz e resolver avidamente todo o problema, sem verificar o que aconteceria se eu começasse de alguma outra posição como por exemplo o canto inferior esquerdo Quando eu resolvi alguns exemplos de diferentes posições iniciais, eu obtinha uma matriz diferente, mas correta em termos de igualdade de linhas e colunas, mas é uma pequena mágica para mim porque isso está acontecendo. Qualquer sugestão apreciada!

Respostas:

1 para resposta № 1

Esse problema pode ser expresso da seguinte maneira.

Suponha que temos n pessoas colhendo morangos,e n cestas. Nosso objetivo é que cada pessoa escolha o mesmo número, e cada cesta tenha o mesmo número (com o número mínimo de morangos extra colhidos.

A matriz A [i, j] representa o número de morangos que a pessoa que coloquei na cesta j.

A ideia é que possamos alcançar esse objetivo simplesmente perguntando a qualquer pessoa que ainda tenha trabalho para colocar um morango em qualquer cesta que não esteja cheia.

isto é não importa qual pessoa ou qual cesta é escolhida, desde que eles ainda tenham espaço. A ordem escolhida no algoritmo fornecido facilita o acompanhamento de quais pessoas e cestas têm espaço.

---