Даден е масив от размер п задачата е стойността на всички елементи да се изравни с минимални разходи . Цената за промяна на стойност от x на y е abs(x - y).
Примери:
конкатенация на java низове
вход: arr[] = [1 100 101]
Изход : 100
Обяснение: Можем да променим всичките му стойности на 100 с минимални разходи
|1 - 100| + |100 - 100| + |101 - 100| = 100Вход : arr [] = [4 6]
Изход : 2
Обяснение: Можем да променим всичките му стойности на 5 с минимални разходи
|4 - 5| + |5 - 6| = 2вход: arr[] = [5 5 5 5]
Изход:
Обяснение: Всички стойности вече са равни.
[Наивен подход] Използване на 2 вложени цикъла - O(n^2) време и O(1) пространство
C++Моля, имайте предвид, че нашият отговор винаги може да бъде една от стойностите на масива. Дори във втория пример по-горе можем алтернативно да направим и двете като 4 или и двете като 6 на една и съща цена.
Идеята е всяка стойност в масива да се разглежда като потенциална целева стойност, след което да се изчисли общата цена на преобразуването на всички други елементи в тази целева стойност. Като проверим всички възможни целеви стойности, можем да намерим тази, която води до минималната обща цена на реализация.java константа
// C++ program to Make all array // elements equal with minimum cost #include
// 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 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# 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 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] Използване на двоично търсене - O(n Log (Range)) време и O(1) интервал
Идеята е да се използва двоично търсене за ефективно намиране на оптималната стойност, към която всички елементи на масива трябва да бъдат преобразувани. Тъй като общата функция на разходите образува изпъкнала крива (първо намаляваща, след това нарастваща) в диапазона от възможни стойности, можем да използваме двоично търсене, за да намерим минималната точка на тази крива, като сравняваме цената в средна точка с цената в средна точка минус едно, което ни казва в коя посока да търсим по-нататък.
Подход стъпка по стъпка:
- Намерете минималните и максималните стойности в масива, за да установите обхвата на търсене
- Използвайте двоично търсене между минималната и максималната стойност, за да намерите оптималната целева стойност
- За всяка пробна стойност изчислете общите разходи за преобразуване на всички елементи на масива към тази стойност
- Сравнете цената в текущата средна точка с цената в средната точка минус едно, за да определите посоката на търсене
- Продължете да стеснявате обхвата на търсене, докато намерите конфигурацията с минимални разходи
// C++ program to Make all array // elements equal with minimum cost #include
// 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 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# 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 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] Използване на сортиране - O(n Log n) време и O(1) пространство
Идеята е да се намери оптималната стойност, на която трябва да бъдат изравнени всички елементи, която трябва да бъде един от съществуващите елементи на масива. Като първо сортираме масива и след това итерираме през всеки елемент като потенциална целева стойност, ние изчисляваме цената на трансформирането на всички други елементи до тази стойност чрез ефективно проследяване на сумата от елементи отляво и отдясно на текущата позиция.
Подход стъпка по стъпка:
- Сортирайте масива, за да обработите елементи във възходящ ред.
- За всеки елемент като потенциална целева стойност изчислете две разходи: извеждане на по-малки елементи нагоре и по-големи елементи надолу.
- Проследявайте сумите отляво и отдясно, за да изчислите ефективно тези разходи за постоянно време на итерация.
- Извеждането на по-малки елементи струва: (текуща стойност × брой по-малки елементи) - (сума от по-малки елементи)
- Намаляването на разходите за по-големи елементи: (сума от по-големи елементи) - (текуща стойност × брой по-големи елементи)
- Сравнете текущата цена с минималната цена.
// C++ program to Make all array // elements equal with minimum cost #include
// 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 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# 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 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Създаване на тест