Dlaczego ten algorytm zawsze działa? Minimalne operacje wymagane, aby każdy rząd i kolumna macierzy były równe - algorytm

Mając kwadratową matrycę o wielkości n x n. Wymagana jest minimalna liczba operacji, aby suma elementów w każdym wierszu i kolumnie była równa. W jednej operacji, zwiększ wartość dowolnej komórki macierzy o 1. W pierwszej linii wymagana jest minimalna operacja drukowania, a w kolejnych wierszach 'n' wypisz 'n' całkowitych reprezentujących ostateczną macierz po operacji.

Wkład:

1 2
3 4

Wydajność:

4
4 3
3 4

Wyjaśnienie

1. Wartość przyrostu komórki (0, 0) o 3
2. Wartość przyrostu komórki (0, 1) o 1 Dlatego wymagane są 4 operacje

Wejście: 9

1 2 3
4 2 3
3 2 1

Wydajność:

6
2 4 3
4 2 3
3 3 3

Wyjaśnienie rozwiązania:

Podejście jest proste, załóżmy, że maxSumjest maksymalną sumą wszystkich wierszy i kolumn. Musimy po prostu zwiększyć kilka komórek tak, aby suma dowolnego wiersza lub kolumny stała się "maxSum". Powiedzmy, że Xi to całkowita liczba operacji potrzebnych do tego, aby suma w wierszu "i" była równa maxSum, a Yj to całkowita liczba operacji potrzebnych do tego, aby suma w kolumnie "j" była równa sumie maksymalnej. Od Xi = Yj więc musimy pracować w jednym z nich zgodnie z warunkiem.

Aby zminimalizować Xi, musimy wybraćmaksimum z rowSumi i colSumj, ponieważ z pewnością doprowadzi to do minimalnego działania. Następnie zwiększ wartość "i" lub "j" w zależności od warunku spełnionego po inkrementacji.

Poniżej znajduje się implementacja powyższego podejścia.

Kod rozwiązania:

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

Moje pytanie:

Nie rozumiem, dlaczego ten kod działa ze wszystkimiprzypadki. To nie jest dla mnie oczywiste, dlaczego rozwiązać problem, który mogę zacząć od lewego górnego rogu matrycy i rozwiązać chciwie cały problem, bez sprawdzania, co by się stało, gdybym zaczął z innej pozycji, na przykład w lewym dolnym rogu w rogu lub w prawym górnym rogu Kiedy rozwiązałem kilka przykładów z innej pozycji wyjściowej, otrzymywałbym inną matrycę, ale poprawną pod względem równości rzędów i kolumn, ale to dla mnie za mało magii, dlaczego tak się dzieje. Wszelkie sugestie doceniane!

Odpowiedzi:

1 dla odpowiedzi № 1

Ten problem można wyrazić w następujący sposób.

Załóżmy, że mamy ludzi zbierających truskawki,i n koszy. Naszym celem jest, aby każda osoba wybrała tę samą liczbę, a każdy koszyk ma ten sam numer (z minimalną liczbą zebranych dodatkowych truskawek.

Macierz A [i, j] reprezentuje liczbę truskawek, które osoba umieściła w koszyku j.

Chodzi o to, że możemy osiągnąć ten cel, po prostu prosząc osobę, która wciąż ma pracę, o umieszczenie truskawki w dowolnym koszyku, który nie jest pełny.

to znaczy nie ma znaczenia, która osoba lub który kosz zostanie wybrany tak długo, jak długo ma jeszcze miejsce. Kolejność wybrana w podanym algorytmie ułatwia śledzenie, które osoby i kosze mają miejsce.

---