logo

TechCodeview

Учините све елементе низа једнаким уз минималне трошкове

Дат низ величина н задатак је да вредност свих елемената буде једнака са минимални трошак . Цена промене вредности са к на и је абс(к - и).

Примери:  

Улаз: арр[] = [1 100 101]
Излаз : 100
Објашњење: Можемо променити све његове вредности на 100 уз минималне трошкове
|1 - 100| + |100 - 100| + |101 - 100| = 100



Инпут : арр[] = [4 6]
Излаз : 2
Објашњење: Можемо променити све његове вредности на 5 уз минималне трошкове
|4 - 5| + |5 - 6| = 2

Улаз: арр[] = [5 5 5 5]
Излаз:
Објашњење: Све вредности су већ једнаке.

[Наивни приступ] Коришћење 2 угнежђене петље - О(н^2) време и О(1) простор

Имајте на уму да наш одговор увек може бити једна од вредности низа. Чак иу другом примеру изнад можемо алтернативно направити оба као 4 или оба као 6 по истој цени.
Идеја је да се свака вредност у низу сматра потенцијалном циљном вредношћу, а затим израчуна укупни трошак претварања свих осталих елемената у ту циљну вредност. Провером свих могућих циљних вредности можемо пронаћи ону која резултира минималним укупним трошковима конверзије.

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

Излаз 
100

[Очекивани приступ – 1] Коришћење бинарне претраге – О(н Лог (Распон)) време и О(1) простор

Идеја је да се користи бинарно претраживање за ефикасно проналажење оптималне вредности у коју треба да се конвертују сви елементи низа. Пошто функција укупних трошкова формира конвексну криву (прво пада, а затим расте) у опсегу могућих вредности, можемо користити бинарну претрагу да лоцирамо минималну тачку ове криве упоређивањем цене у средњој тачки са ценом у средњој тачки минус један што нам говори у ком правцу да тражимо даље.

Приступ корак по корак:

  1. Пронађите минималне и максималне вредности у низу да бисте успоставили опсег претраге
  2. Користите бинарну претрагу између минималне и максималне вредности да бисте лоцирали оптималну циљну вредност
  3. За сваку пробну вредност израчунајте укупан трошак претварања свих елемената низа у ту вредност
  4. Упоредите цену на тренутној средини са ценом на средини минус један да бисте одредили правац претраге
  5. Наставите да сужавате опсег претраге док не пронађете конфигурацију минималне цене
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));

Излаз 
100

[Очекивани приступ - 2] Коришћење сортирања - О(н Лог н) време и О(1) простор

Идеја је да се пронађе оптимална вредност на коју треба да се изједначе сви елементи који морају бити један од постојећих елемената низа. Прво сортирањем низа, а затим итерацијом кроз сваки елемент као потенцијалну циљну вредност, израчунавамо цену трансформације свих осталих елемената у ту вредност ефикасним праћењем збира елемената лево и десно од тренутне позиције.

Приступ корак по корак:

  1. Сортирајте низ за обраду елемената у растућем редоследу.
  2. За сваки елемент као потенцијалну циљну вредност израчунајте два трошка: подизање мањих елемената и смањење већих елемената.
  3. Пратите леви и десни збир да бисте ефикасно израчунали ове трошкове у константном времену по итерацији.
    • Повећање трошкова мањих елемената: (тренутна вредност × број мањих елемената) - (збир мањих елемената)
    • Смањење трошкова већих елемената: (збир већих елемената) - (тренутна вредност × број већих елемената)
  4. Упоредите тренутне трошкове са минималним трошковима.
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));

Излаз 
100
Креирај квиз