Rendi uguali tutti gli elementi dell'array con un costo minimo
Data una matrice di dimensioni N il compito è rendere uguale il valore di tutti gli elementi costo minimo . Il costo per modificare un valore da x a y è addominali(x - y).
Esempi:
Ingresso: arr[] = [1 100 101]
Produzione : 100
Spiegazione: Possiamo modificare tutti i suoi valori in 100 con un costo minimo
|1 - 100| + |100 - 100| + |101 - 100| = 100Ingresso : arr[] = [4 6]
Produzione : 2
Spiegazione: Possiamo cambiare tutti i suoi valori in 5 con un costo minimo
|4 - 5| + |5 - 6| = 2Ingresso: arr[] = [5 5 5 5]
Produzione:
Spiegazione: Tutti i valori sono già uguali.
[Approccio ingenuo] Utilizzo di 2 cicli nidificati: tempo O (n ^ 2) e spazio O (1).
C++Tieni presente che la nostra risposta può sempre essere uno dei valori dell'array. Anche nel secondo esempio sopra possiamo in alternativa realizzarli entrambi come 4 oppure entrambi come 6 allo stesso costo..
L'idea è di considerare ciascun valore nell'array come un potenziale valore target, quindi calcolare il costo totale della conversione di tutti gli altri elementi in quel valore target. Controllando tutti i possibili valori target possiamo trovare quello che si traduce nel costo complessivo minimo di conversione.
// 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 ));
Produzione
100
[Approccio previsto - 1] Utilizzo della ricerca binaria - Tempo O(n Log (intervallo)) e spazio O(1)
L'idea è di utilizzare la ricerca binaria per trovare in modo efficiente il valore ottimale in cui convertire tutti gli elementi dell'array. Poiché la funzione di costo totale forma una curva convessa (prima decrescente e poi crescente) nell'intervallo di valori possibili, possiamo utilizzare la ricerca binaria per individuare il punto minimo di questa curva confrontando il costo al punto medio con il costo al punto medio meno uno che ci dice in quale direzione cercare ulteriormente.
Approccio passo dopo passo:
- Trova i valori minimo e massimo nell'array per stabilire l'intervallo di ricerca
- Utilizzare la ricerca binaria tra i valori minimo e massimo per individuare il valore target ottimale
- Per ogni valore di prova calcolare il costo totale della conversione di tutti gli elementi dell'array in quel valore
- Confronta il costo al punto medio attuale con il costo al punto medio meno uno per determinare la direzione della ricerca
- Continua a restringere l'intervallo di ricerca fino a trovare la configurazione di costo minimo
// 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 ));
Produzione
100
[Approccio previsto - 2] Utilizzo dell'ordinamento - O(n Log n) tempo e O(1) spazio
L'idea è trovare il valore ottimale al quale tutti gli elementi dovrebbero essere equalizzati, che deve essere uno degli elementi dell'array esistente. Ordinando prima l'array e poi scorrendo ciascun elemento come potenziale valore target, calcoliamo il costo di trasformare tutti gli altri elementi in quel valore monitorando in modo efficiente la somma degli elementi a sinistra e a destra della posizione corrente.
Approccio passo dopo passo:
- Ordina l'array per elaborare gli elementi in ordine crescente.
- Per ciascun elemento come potenziale valore target calcolare due costi: portare in alto gli elementi più piccoli e abbassare gli elementi più grandi.
- Tieni traccia delle somme sinistra e destra per calcolare questi costi in modo efficiente in tempo costante per iterazione.
- Aumentare i costi degli elementi più piccoli: (valore corrente × numero di elementi più piccoli) - (somma degli elementi più piccoli)
- Riduzione dei costi degli elementi più grandi: (somma degli elementi più grandi) - (valore attuale × numero di elementi più grandi)
- Confrontare il costo attuale con il costo minimo.
// 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 ));
Produzione
100Crea quiz
![Come verificare chi ha visualizzato i momenti salienti di Instagram [2024]](https://techcodeview.com/img/how/24/how-check-who-viewed-instagram-highlights.webp)
