logo

TechCodeview

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).

susedné uhly

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| = 100



Vstup : 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| = 2

Vstup: 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

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++ 
// 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:

  1. Nájdite minimálne a maximálne hodnoty v poli a vytvorte rozsah vyhľadávania
  2. Na nájdenie optimálnej cieľovej hodnoty použite binárne vyhľadávanie medzi minimálnou a maximálnou hodnotou
  3. Pre každú skúšobnú hodnotu vypočítajte celkové náklady na konverziu všetkých prvkov poľa na túto hodnotu
  4. Ak chcete určiť smer vyhľadávania, porovnajte cenu v aktuálnom strede s cenou v strede mínus jedna
  5. Pokračujte v zužovaní rozsahu vyhľadávania, kým nenájdete konfiguráciu minimálnych nákladov
C++ 
// 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:

  1. Zoraďte pole na spracovanie prvkov vo vzostupnom poradí.
  2. 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.
  3. 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)
  4. Porovnajte súčasné náklady s minimálnymi nákladmi.
C++ 
// 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 
100
Vytvoriť kvíz