Padarykite visus masyvo elementus vienodus su minimaliomis sąnaudomis
Atsižvelgiant į dydžių masyvą n užduotis yra padaryti visų elementų vertę lygią su minimalios išlaidos . Vertės keitimo iš x į y kaina yra abs(x - y).
Pavyzdžiai:
Įvestis: arr[] = [1 100 101]
Išvestis : 100
Paaiškinimas: Visas jo vertes galime pakeisti į 100 su minimaliomis sąnaudomis
|1 - 100| + |100 - 100| + |101 - 100| = 100Įvestis : arr[] = [4 6]
Išvestis : 2
Paaiškinimas: Visas jo reikšmes galime pakeisti į 5 su minimaliomis sąnaudomis
|4 - 5| + |5 - 6| = 2Įvestis: arr[] = [5 5 5 5]
Išvestis:
Paaiškinimas: Visos vertės jau lygios.
[Naivus požiūris] Naudojant 2 įdėtas kilpas – O(n^2) laikas ir O(1) erdvė
C++Atminkite, kad mūsų atsakymas visada gali būti viena iš masyvo reikšmių. Net antrajame aukščiau pateiktame pavyzdyje galime pakeisti abu kaip 4 arba abu kaip 6 už tą pačią kainą.
Idėja yra atsižvelgti į kiekvieną masyvo vertę kaip potencialią tikslinę vertę, tada apskaičiuoti visas išlaidas, skirtas visų kitų elementų konvertavimui į tą tikslinę vertę. Patikrinę visas galimas tikslines vertes galime rasti tą, kuri lemia minimalų bendrą konversijos mokestį.
// 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 ));
Išvestis
100
[Numatomas požiūris – 1] Naudojant dvejetainę paiešką – O(n Log (diapazonas)) laikas ir O(1) erdvė
Idėja yra naudoti dvejetainę paiešką, kad būtų galima efektyviai rasti optimalią vertę, į kurią turėtų būti konvertuojami visi masyvo elementai. Kadangi bendrųjų išlaidų funkcija sudaro išgaubtą kreivę (pirmiausia mažėja, o paskui didėja) galimų verčių diapazone, galime naudoti dvejetainę paiešką, kad surastume mažiausią šios kreivės tašką, palygindami kainą viduryje su vidurio taško kaina atėmus vieną, kuri nurodo, kuria kryptimi ieškoti toliau.
Žingsnis po žingsnio požiūris:
- Raskite mažiausią ir didžiausią masyvo reikšmes, kad nustatytumėte paieškos diapazoną
- Norėdami rasti optimalią tikslinę vertę, naudokite dvejetainę paiešką tarp minimalių ir didžiausių verčių
- Kiekvienai bandomajai vertei apskaičiuokite bendrą visų masyvo elementų konvertavimo į tą vertę išlaidas
- Palyginkite kainą dabartiniame vidurio taške su kaina viduryje, atėmus vieną, kad nustatytumėte paieškos kryptį
- Toliau siaurinkite paieškos diapazoną, kol rasite minimalios kainos konfigūraciją
// 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 ));
Išvestis
100
[Numatomas požiūris – 2] Rūšiavimo naudojimas – O(n Log n) laikas ir O(1) erdvė
Idėja yra rasti optimalią reikšmę, kuriai turėtų būti išlyginti visi elementai, kurie turi būti vienas iš esamų masyvo elementų. Pirmiausia rūšiuodami masyvą, o po to kartodami kiekvieną elementą kaip potencialią tikslinę vertę, apskaičiuojame visų kitų elementų transformavimo į tą vertę kainą, efektyviai stebėdami elementų sumą kairėje ir dešinėje nuo dabartinės padėties.
Žingsnis po žingsnio požiūris:
- Rūšiuokite masyvą, kad apdorotumėte elementus didėjančia tvarka.
- Kiekvienam elementui kaip potencialiai tikslinei vertei apskaičiuokite dvi išlaidas: mažesnių elementų pakėlimą aukštyn ir didesnių elementų mažinimą.
- Stebėkite kairę ir dešinę sumas, kad efektyviai apskaičiuotumėte šias išlaidas pastoviu iteracijos laiku.
- Mažesnių elementų padidinimas: (dabartinė vertė × mažesnių elementų skaičius) - (mažesnių elementų suma)
- Didesnių elementų sumažinimas: (didesnių elementų suma) - (dabartinė vertė × didesnių elementų skaičius)
- Palyginkite dabartinę kainą su minimaliomis išlaidomis.
// 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 ));
Išvestis
100Sukurti viktoriną
