Tegye egyenlővé az összes tömbelemet minimális költséggel
Adott egy sor méret n a feladat az összes elem értékét egyenlővé tenni minimális költség . Egy érték x-ről y-ra változtatásának költsége a következő abs(x - y).
Példák:
Bemenet: arr[] = [1 100 101]
Kimenet : 100
Magyarázat: Minden értékét minimális költséggel 100-ra tudjuk változtatni
|1 - 100| + |100 - 100| + |101 - 100| = 100Bemenet : arr[] = [4 6]
Kimenet : 2
Magyarázat: Minden értékét minimális költséggel 5-re módosíthatjuk
|4 - 5| + |5 - 6| = 2Bemenet: arr[] = [5 5 5 5]
Kimenet:
Magyarázat: Már minden érték egyenlő.
[Naiv megközelítés] 2 egymásba ágyazott hurok használata – O(n^2) idő és O(1) tér
C++Kérjük, vegye figyelembe, hogy a válaszunk mindig lehet a tömbértékek egyike. Még a fenti második példában is elkészíthetjük mindkettőt 4-nek, vagy mindkettőt 6-nak azonos áron.
Az ötlet az, hogy a tömb minden egyes értékét potenciális célértéknek tekintsük, majd kiszámítsuk az összes többi elem célértékre való konvertálásának teljes költségét. Az összes lehetséges célérték ellenőrzésével megtalálhatjuk azt, amelyik a minimális konverziós összköltséget eredményezi.
// 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 ));
Kimenet
100
[Várható megközelítés - 1] Bináris keresés használata - O(n Log (Tartomány)) idő és O(1) tér
Az ötlet az, hogy a bináris keresés segítségével hatékonyan megtaláljuk azt az optimális értéket, amelyre az összes tömbelemet konvertálni kell. Mivel az összköltség függvény konvex görbét képez (először csökkenő, majd növekvő) a lehetséges értékek tartományában, bináris keresést használhatunk a görbe minimumpontjának megkeresésére, összehasonlítva a középponti költséget a középponti költséggel, mínusz az egyikkel, ami megmondja, hogy melyik irányba kell tovább keresni.
Lépésről lépésre megközelítés:
- Keresse meg a minimális és maximális értéket a tömbben a keresési tartomány meghatározásához
- Használjon bináris keresést a minimális és maximális értékek között az optimális célérték megkereséséhez
- Minden próbaértékhez számítsa ki az összes tömbelem adott értékre konvertálásának teljes költségét
- Hasonlítsa össze a jelenlegi középponti költséget a középponti költséggel mínusz egy a keresési irány meghatározásához
- Folytassa a keresési tartomány szűkítését, amíg meg nem találja a minimális költség konfigurációt
// 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 ));
Kimenet
100
[Várható megközelítés - 2] Rendezés használata - O(n Log n) idő és O(1) tér
Az ötlet az, hogy megtaláljuk azt az optimális értéket, amelyre minden elemet ki kell egyenlíteni, aminek a meglévő tömbelemek egyikének kell lennie. Ha először rendezi a tömböt, majd minden elemet potenciális célértékként iterál, kiszámítjuk az összes többi elem adott értékre való átalakításának költségét azáltal, hogy hatékonyan követjük az aktuális pozíciótól balra és jobbra eső elemek összegét.
Lépésről lépésre megközelítés:
- Rendezze a tömböt az elemek feldolgozásához növekvő sorrendben.
- Minden elemre, mint potenciális célértékre két költséget számítson ki: a kisebb elemek felemelése és a nagyobb elemek leépítése.
- Kövesse nyomon a bal és a jobb oldali összegeket, hogy ezeket a költségeket hatékonyan, iterációnkénti állandó időben számítsa ki.
- Kisebb elemek költségnövelése: (jelenlegi érték × kisebb elemek száma) - (kisebb elemek összege)
- Nagyobb elemek költségcsökkentése: (nagyobb elemek összege) - (jelenlegi érték × nagyobb elemek száma)
- Hasonlítsa össze az aktuális költséget a minimális költséggel.
// 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 ));
Kimenet
100Kvíz létrehozása
