Feu que tots els elements de la matriu siguin iguals amb un cost mínim
Donada una sèrie de mides n la tasca és igualar el valor de tots els elements amb cost mínim . El cost de canviar un valor de x a y és abs (x - y).
Exemples:
Entrada: arr[] = [1 100 101]
Sortida : 100
Explicació: Podem canviar tots els seus valors a 100 amb un cost mínim
|1 - 100| + |100 - 100| + |101 - 100| = 100Entrada : arr[] = [4 6]
Sortida : 2
Explicació: Podem canviar tots els seus valors a 5 amb un cost mínim
|4 - 5| + |5 - 6| = 2Entrada: arr[] = [5 5 5 5]
Sortida:
Explicació: Tots els valors ja són iguals.
[Enfocament ingenu] Ús de 2 bucles imbricats: temps O(n^2) i espai O(1)
C++Tingueu en compte que la nostra resposta sempre pot ser un dels valors de la matriu. Fins i tot en el segon exemple anterior, podem fer-ho alternativament com a 4 o tots dos com a 6 al mateix cost.
La idea és considerar cada valor de la matriu com un valor objectiu potencial i després calcular el cost total de convertir tots els altres elements a aquest valor objectiu. En comprovar tots els valors objectiu possibles, podem trobar el que produeix el cost global mínim de conversió.
// C++ program to Make all array // elements equal with minimum cost #include using namespace std ; // Function which finds the minimum // cost to make array elements equal int minCost ( vector < int > & arr ) { int n = arr . size (); int ans = INT_MAX ; // Try each element as the target value for ( int i = 0 ; i < n ; i ++ ) { int currentCost = 0 ; // Calculate cost of making all // elements equal to arr[i] for ( int j = 0 ; j < n ; j ++ ) { currentCost += abs ( arr [ j ] - arr [ i ]); } // Update minimum cost if current cost is lower ans = min ( ans currentCost ); } return ans ; } int main () { vector < int > arr = { 1 100 101 }; cout < < minCost ( arr ) < < endl ; return 0 ; }
Java // Java program to Make all array // elements equal with minimum cost import java.util.* ; class GfG { // Function which finds the minimum // cost to make array elements equal static int minCost ( int [] arr ) { int n = arr . length ; int ans = Integer . MAX_VALUE ; // Try each element as the target value for ( int i = 0 ; i < n ; i ++ ) { int currentCost = 0 ; // Calculate cost of making all // elements equal to arr[i] for ( int j = 0 ; j < n ; j ++ ) { currentCost += Math . abs ( arr [ j ] - arr [ i ] ); } // Update minimum cost if current cost is lower ans = Math . min ( ans currentCost ); } return ans ; } public static void main ( String [] args ) { int [] arr = { 1 100 101 }; System . out . println ( minCost ( arr )); } }
Python # Python program to Make all array # elements equal with minimum cost # Function which finds the minimum # cost to make array elements equal def minCost ( arr ): n = len ( arr ) ans = float ( 'inf' ) # Try each element as the target value for i in range ( n ): currentCost = 0 # Calculate cost of making all # elements equal to arr[i] for j in range ( n ): currentCost += abs ( arr [ j ] - arr [ i ]) # Update minimum cost if current cost is lower ans = min ( ans currentCost ) return ans if __name__ == '__main__' : arr = [ 1 100 101 ] print ( minCost ( arr ))
C# // C# program to Make all array // elements equal with minimum cost using System ; class GfG { // Function which finds the minimum // cost to make array elements equal static int minCost ( int [] arr ) { int n = arr . Length ; int ans = int . MaxValue ; // Try each element as the target value for ( int i = 0 ; i < n ; i ++ ) { int currentCost = 0 ; // Calculate cost of making all // elements equal to arr[i] for ( int j = 0 ; j < n ; j ++ ) { currentCost += Math . Abs ( arr [ j ] - arr [ i ]); } // Update minimum cost if current cost is lower ans = Math . Min ( ans currentCost ); } return ans ; } static void Main () { int [] arr = { 1 100 101 }; Console . WriteLine ( minCost ( arr )); } }
JavaScript // JavaScript program to Make all array // elements equal with minimum cost // Function which finds the minimum // cost to make array elements equal function minCost ( arr ) { let n = arr . length ; let ans = Number . MAX_SAFE_INTEGER ; // Try each element as the target value for ( let i = 0 ; i < n ; i ++ ) { let currentCost = 0 ; // Calculate cost of making all // elements equal to arr[i] for ( let j = 0 ; j < n ; j ++ ) { currentCost += Math . abs ( arr [ j ] - arr [ i ]); } // Update minimum cost if current cost is lower ans = Math . min ( ans currentCost ); } return ans ; } let arr = [ 1 100 101 ]; console . log ( minCost ( arr ));
Sortida
100
[Enfocament esperat - 1] Ús de la cerca binària - O(n Log (Range)) temps i O (1) espai
La idea és utilitzar la cerca binària per trobar de manera eficient el valor òptim al qual s'han de convertir tots els elements de la matriu. Com que la funció de cost total forma una corba convexa (primer decreixent i després creixent) a través de l'interval de valors possibles, podem utilitzar la cerca binària per localitzar el punt mínim d'aquesta corba comparant el cost en un punt mig amb el cost a mig punt menys un que ens indica quina direcció hem de cercar més endavant.
Enfocament pas a pas:
- Trobeu els valors mínims i màxims a la matriu per establir l'interval de cerca
- Utilitzeu la cerca binària entre els valors mínim i màxim per localitzar el valor objectiu òptim
- Per a cada valor de prova, calculeu el cost total de convertir tots els elements de la matriu a aquest valor
- Compareu el cost al punt mitjà actual amb el cost al punt mig menys un per determinar la direcció de la cerca
- Continueu reduint l'interval de cerca fins a trobar la configuració de cost mínim
// C++ program to Make all array // elements equal with minimum cost #include using namespace std ; // Function to find the cost of changing // array values to mid. int findCost ( vector < int > & arr int mid ) { int n = arr . size (); int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { ans += abs ( arr [ i ] - mid ); } return ans ; } // Function which finds the minimum cost // to make array elements equal. int minCost ( vector < int > & arr ) { int n = arr . size (); int mini = INT_MAX maxi = INT_MIN ; // Find the minimum and maximum value. for ( int i = 0 ; i < n ; i ++ ) { mini = min ( mini arr [ i ]); maxi = max ( maxi arr [ i ]); } int s = mini e = maxi ; int ans = INT_MAX ; while ( s <= e ) { int mid = s + ( e - s ) / 2 ; int cost1 = findCost ( arr mid ); int cost2 = findCost ( arr mid -1 ); if ( cost1 < cost2 ) { ans = cost1 ; s = mid + 1 ; } else { e = mid - 1 ; } } return ans ; } int main () { vector < int > arr = { 1 100 101 }; cout < < minCost ( arr ); return 0 ; }
Java // Java program to Make all array // elements equal with minimum cost import java.util.* ; class GfG { // Function to find the cost of changing // array values to mid. static int findCost ( int [] arr int mid ) { int n = arr . length ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { ans += Math . abs ( arr [ i ] - mid ); } return ans ; } // Function which finds the minimum cost // to make array elements equal. static int minCost ( int [] arr ) { int n = arr . length ; int mini = Integer . MAX_VALUE maxi = Integer . MIN_VALUE ; // Find the minimum and maximum value. for ( int i = 0 ; i < n ; i ++ ) { mini = Math . min ( mini arr [ i ] ); maxi = Math . max ( maxi arr [ i ] ); } int s = mini e = maxi ; int ans = Integer . MAX_VALUE ; while ( s <= e ) { int mid = s + ( e - s ) / 2 ; int cost1 = findCost ( arr mid ); int cost2 = findCost ( arr mid - 1 ); if ( cost1 < cost2 ) { ans = cost1 ; s = mid + 1 ; } else { e = mid - 1 ; } } return ans ; } public static void main ( String [] args ) { int [] arr = { 1 100 101 }; System . out . println ( minCost ( arr )); } }
Python # Python program to Make all array # elements equal with minimum cost # Function to find the cost of changing # array values to mid. def findCost ( arr mid ): n = len ( arr ) ans = 0 for i in range ( n ): ans += abs ( arr [ i ] - mid ) return ans # Function which finds the minimum cost # to make array elements equal. def minCost ( arr ): n = len ( arr ) mini = float ( 'inf' ) maxi = float ( '-inf' ) # Find the minimum and maximum value. for i in range ( n ): mini = min ( mini arr [ i ]) maxi = max ( maxi arr [ i ]) s = mini e = maxi ans = float ( 'inf' ) while s <= e : mid = s + ( e - s ) // 2 cost1 = findCost ( arr mid ) cost2 = findCost ( arr mid - 1 ) if cost1 < cost2 : ans = cost1 s = mid + 1 else : e = mid - 1 return ans if __name__ == '__main__' : arr = [ 1 100 101 ] print ( minCost ( arr ))
C# // C# program to Make all array // elements equal with minimum cost using System ; class GfG { // Function to find the cost of changing // array values to mid. static int findCost ( int [] arr int mid ) { int n = arr . Length ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { ans += Math . Abs ( arr [ i ] - mid ); } return ans ; } // Function which finds the minimum cost // to make array elements equal. static int minCost ( int [] arr ) { int n = arr . Length ; int mini = int . MaxValue maxi = int . MinValue ; // Find the minimum and maximum value. for ( int i = 0 ; i < n ; i ++ ) { mini = Math . Min ( mini arr [ i ]); maxi = Math . Max ( maxi arr [ i ]); } int s = mini e = maxi ; int ans = int . MaxValue ; while ( s <= e ) { int mid = s + ( e - s ) / 2 ; int cost1 = findCost ( arr mid ); int cost2 = findCost ( arr mid - 1 ); if ( cost1 < cost2 ) { ans = cost1 ; s = mid + 1 ; } else { e = mid - 1 ; } } return ans ; } static void Main () { int [] arr = { 1 100 101 }; Console . WriteLine ( minCost ( arr )); } }
JavaScript // JavaScript program to Make all array // elements equal with minimum cost // Function to find the cost of changing // array values to mid. function findCost ( arr mid ) { let n = arr . length ; let ans = 0 ; for ( let i = 0 ; i < n ; i ++ ) { ans += Math . abs ( arr [ i ] - mid ); } return ans ; } // Function which finds the minimum cost // to make array elements equal. function minCost ( arr ) { let n = arr . length ; let mini = Number . MAX_SAFE_INTEGER maxi = Number . MIN_SAFE_INTEGER ; // Find the minimum and maximum value. for ( let i = 0 ; i < n ; i ++ ) { mini = Math . min ( mini arr [ i ]); maxi = Math . max ( maxi arr [ i ]); } let s = mini e = maxi ; let ans = Number . MAX_SAFE_INTEGER ; while ( s <= e ) { let mid = Math . floor ( s + ( e - s ) / 2 ); let cost1 = findCost ( arr mid ); let cost2 = findCost ( arr mid - 1 ); if ( cost1 < cost2 ) { ans = cost1 ; s = mid + 1 ; } else { e = mid - 1 ; } } return ans ; } let arr = [ 1 100 101 ]; console . log ( minCost ( arr ));
Sortida
100
[Enfocament esperat - 2] Ús de l'ordenació - O(n Log n) temps i O (1) espai
La idea és trobar el valor òptim al qual s'han d'igualar tots els elements que ha de ser un dels elements de matriu existents. En ordenar primer la matriu i després iterant a través de cada element com a valor objectiu potencial, calculem el cost de transformar tots els altres elements a aquest valor fent un seguiment eficient de la suma d'elements a l'esquerra i a la dreta de la posició actual.
Enfocament pas a pas:
- Ordena la matriu per processar els elements en ordre ascendent.
- Per a cada element com a valor objectiu potencial, calculeu dos costos: augmentar els elements més petits i baixar els elements més grans.
- Feu un seguiment de les sumes esquerra i dreta per calcular aquests costos de manera eficient en temps constant per iteració.
- Augment dels costos d'elements més petits: (valor actual × nombre d'elements més petits) - (suma d'elements més petits)
- Reduint els costos d'elements més grans: (suma d'elements més grans) - (valor actual × nombre d'elements més grans)
- Compareu el cost actual amb el cost mínim.
// C++ program to Make all array // elements equal with minimum cost #include using namespace std ; // Function which finds the minimum cost // to make array elements equal. int minCost ( vector < int > & arr ) { int n = arr . size (); // Sort the array sort ( arr . begin () arr . end ()); // Variable to store sum of elements // to the right side. int right = 0 ; for ( int i = 0 ; i < n ; i ++ ) { right += arr [ i ]; } int ans = INT_MAX ; int left = 0 ; for ( int i = 0 ; i < n ; i ++ ) { // Remove the current element from right sum. right -= arr [ i ]; // Find cost of incrementing left side elements int leftCost = i * arr [ i ] - left ; // Find cost of decrementing right side elements. int rightCost = right - ( n -1 - i ) * arr [ i ]; ans = min ( ans leftCost + rightCost ); // Add current value to left sum left += arr [ i ]; } return ans ; } int main () { vector < int > arr = { 1 100 101 }; cout < < minCost ( arr ); return 0 ; }
Java // Java program to Make all array // elements equal with minimum cost import java.util.* ; class GfG { // Function which finds the minimum cost // to make array elements equal. static int minCost ( int [] arr ) { int n = arr . length ; // Sort the array Arrays . sort ( arr ); // Variable to store sum of elements // to the right side. int right = 0 ; for ( int i = 0 ; i < n ; i ++ ) { right += arr [ i ] ; } int ans = Integer . MAX_VALUE ; int left = 0 ; for ( int i = 0 ; i < n ; i ++ ) { // Remove the current element from right sum. right -= arr [ i ] ; // Find cost of incrementing left side elements int leftCost = i * arr [ i ] - left ; // Find cost of decrementing right side elements. int rightCost = right - ( n - 1 - i ) * arr [ i ] ; ans = Math . min ( ans leftCost + rightCost ); // Add current value to left sum left += arr [ i ] ; } return ans ; } public static void main ( String [] args ) { int [] arr = { 1 100 101 }; System . out . println ( minCost ( arr )); } }
Python # Python program to Make all array # elements equal with minimum cost # Function which finds the minimum cost # to make array elements equal. def minCost ( arr ): n = len ( arr ) # Sort the array arr . sort () # Variable to store sum of elements # to the right side. right = sum ( arr ) ans = float ( 'inf' ) left = 0 for i in range ( n ): # Remove the current element from right sum. right -= arr [ i ] # Find cost of incrementing left side elements leftCost = i * arr [ i ] - left # Find cost of decrementing right side elements. rightCost = right - ( n - 1 - i ) * arr [ i ] ans = min ( ans leftCost + rightCost ) # Add current value to left sum left += arr [ i ] return ans if __name__ == '__main__' : arr = [ 1 100 101 ] print ( minCost ( arr ))
C# // C# program to Make all array // elements equal with minimum cost using System ; class GfG { // Function which finds the minimum cost // to make array elements equal. static int minCost ( int [] arr ) { int n = arr . Length ; // Sort the array Array . Sort ( arr ); // Variable to store sum of elements // to the right side. int right = 0 ; for ( int i = 0 ; i < n ; i ++ ) { right += arr [ i ]; } int ans = int . MaxValue ; int left = 0 ; for ( int i = 0 ; i < n ; i ++ ) { // Remove the current element from right sum. right -= arr [ i ]; // Find cost of incrementing left side elements int leftCost = i * arr [ i ] - left ; // Find cost of decrementing right side elements. int rightCost = right - ( n - 1 - i ) * arr [ i ]; ans = Math . Min ( ans leftCost + rightCost ); // Add current value to left sum left += arr [ i ]; } return ans ; } static void Main () { int [] arr = { 1 100 101 }; Console . WriteLine ( minCost ( arr )); } }
JavaScript // JavaScript program to Make all array // elements equal with minimum cost // Function which finds the minimum cost // to make array elements equal. function minCost ( arr ) { let n = arr . length ; // Sort the array arr . sort (( a b ) => a - b ); // Variable to store sum of elements // to the right side. let right = 0 ; for ( let i = 0 ; i < n ; i ++ ) { right += arr [ i ]; } let ans = Number . MAX_SAFE_INTEGER ; let left = 0 ; for ( let i = 0 ; i < n ; i ++ ) { // Remove the current element from right sum. right -= arr [ i ]; // Find cost of incrementing left side elements let leftCost = i * arr [ i ] - left ; // Find cost of decrementing right side elements. let rightCost = right - ( n - 1 - i ) * arr [ i ]; ans = Math . min ( ans leftCost + rightCost ); // Add current value to left sum left += arr [ i ]; } return ans ; } let arr = [ 1 100 101 ]; console . log ( minCost ( arr ));
Sortida
100Crea un qüestionari
