Urobte všetky prvky poľa rovnaké s minimálnymi nákladmi
Vzhľadom na pole veľkosti n úlohou je dosiahnuť rovnakú hodnotu všetkých prvkov minimálne náklady . Náklady na zmenu hodnoty z x na y sú abs(x - y).
Príklady:
Vstup: arr[] = [1 100 101]
Výstup : 100
Vysvetlenie: Môžeme zmeniť všetky jeho hodnoty na 100 s minimálnymi nákladmi
|1 – 100| + |100 - 100| + |101 - 100| = 100Vstup : arr[] = [4 6]
Výstup : 2
Vysvetlenie: Môžeme zmeniť všetky jeho hodnoty na 5 s minimálnymi nákladmi
|4 - 5| + |5 - 6| = 2Vstup: arr[] = [5 5 5 5]
výstup:
Vysvetlenie: Všetky hodnoty sú už rovnaké.
[Naivný prístup] Použitie 2 vnorených slučiek – O(n^2) čas a O(1) priestor
C++Upozorňujeme, že našou odpoveďou môže byť vždy jedna z hodnôt poľa. Aj v druhom príklade vyššie môžeme alternatívne vyrobiť oba ako 4 alebo oboje ako 6 za rovnakú cenu.
Cieľom je zvážiť každú hodnotu v poli ako potenciálnu cieľovú hodnotu a potom vypočítať celkové náklady na konverziu všetkých ostatných prvkov na túto cieľovú hodnotu. Kontrolou všetkých možných cieľových hodnôt môžeme nájsť tú, ktorá vedie k minimálnym celkovým nákladom na konverziu.
// 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 ));
Výstup
100
[Očakávaný prístup - 1] Použitie binárneho vyhľadávania - O(n Log (Rozsah)) čas a O(1) priestor
Cieľom je využiť binárne vyhľadávanie na efektívne nájdenie optimálnej hodnoty, na ktorú by sa mali previesť všetky prvky poľa. Keďže funkcia celkových nákladov tvorí konvexnú krivku (najskôr klesajúcu a potom rastúcu) naprieč rozsahom možných hodnôt, môžeme použiť binárne vyhľadávanie na nájdenie minimálneho bodu tejto krivky porovnaním nákladov v strede s nákladmi v strede mínus jedna, čo nám povie, ktorým smerom ďalej hľadať.
Postup krok za krokom:
- Nájdite minimálne a maximálne hodnoty v poli a vytvorte rozsah vyhľadávania
- Na nájdenie optimálnej cieľovej hodnoty použite binárne vyhľadávanie medzi minimálnou a maximálnou hodnotou
- Pre každú skúšobnú hodnotu vypočítajte celkové náklady na konverziu všetkých prvkov poľa na túto hodnotu
- Ak chcete určiť smer vyhľadávania, porovnajte cenu v aktuálnom strede s cenou v strede mínus jedna
- Pokračujte v zužovaní rozsahu vyhľadávania, kým nenájdete konfiguráciu minimálnych nákladov
// 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 ));
Výstup
100
[Očakávaný prístup - 2] Použitie triedenia - O(n Log n) čas a O(1) priestor
Cieľom je nájsť optimálnu hodnotu, na ktorú by sa mali vyrovnať všetky prvky, čo musí byť jeden z existujúcich prvkov poľa. Prvým triedením poľa a následným opakovaním každého prvku ako potenciálnej cieľovej hodnoty vypočítame náklady na transformáciu všetkých ostatných prvkov na túto hodnotu efektívnym sledovaním súčtu prvkov naľavo a napravo od aktuálnej pozície.
Postup krok za krokom:
- Zoraďte pole na spracovanie prvkov vo vzostupnom poradí.
- Pre každý prvok ako potenciálnu cieľovú hodnotu vypočítajte dve náklady: vynesenie menších prvkov hore a väčšie prvky dole.
- Sledujte súčty vľavo a vpravo, aby ste tieto náklady vypočítali efektívne v konštantnom čase na jednu iteráciu.
- Zvýšenie nákladov na menšie prvky: (aktuálna hodnota × počet menších prvkov) - (súčet menších prvkov)
- Zníženie nákladov na väčšie prvky: (súčet väčších prvkov) - (aktuálna hodnota × počet väčších prvkov)
- Porovnajte súčasné náklady s minimálnymi nákladmi.
// 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 ));
Výstup
100Vytvoriť kvíz
