Dada uma matriz de tamanho n a tarefa é tornar o valor de todos os elementos igual a custo mínimo . O custo de mudar um valor de x para y é abs(x - y).
Exemplos:
Entrada: arr[] = [1 100 101]
Saída : 100
Explicação: Podemos alterar todos os seus valores para 100 com custo mínimo
|1 - 100| + |100 - 100| + |101 - 100| = 100Entrada : arr[] = [4 6]
Saída : 2
Explicação: Podemos alterar todos os seus valores para 5 com custo mínimo
|4 - 5| + |5 - 6| = 2Entrada: arr[] = [5 5 5 5]
Saída:
Explicação: Todos os valores já são iguais.
[Abordagem ingênua] Usando 2 loops aninhados - tempo O (n ^ 2) e espaço O (1)
C++Observe que nossa resposta sempre pode ser um dos valores do array. Mesmo no segundo exemplo acima, podemos alternativamente fazer ambos como 4 ou ambos como 6 pelo mesmo custo.
A ideia é considerar cada valor na matriz como um valor alvo potencial e depois calcular o custo total de conversão de todos os outros elementos para esse valor alvo. Ao verificar todos os valores-alvo possíveis, podemos encontrar aquele que resulta no custo geral mínimo de conversão.
// 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));
Saída
100
[Abordagem esperada - 1] Usando pesquisa binária - tempo O(n Log (Range)) e espaço O(1)
A ideia é utilizar a pesquisa binária para encontrar com eficiência o valor ideal para o qual todos os elementos do array devem ser convertidos. Como a função de custo total forma uma curva convexa (primeiro decrescente e depois crescente) em toda a gama de valores possíveis, podemos usar a pesquisa binária para localizar o ponto mínimo desta curva, comparando o custo no ponto médio com o custo no ponto médio menos um, o que nos diz em qual direção pesquisar mais.
Abordagem passo a passo:
- Encontre os valores mínimo e máximo na matriz para estabelecer o intervalo de pesquisa
- Use a pesquisa binária entre os valores mínimo e máximo para localizar o valor alvo ideal
- Para cada valor experimental, calcule o custo total de conversão de todos os elementos da matriz para esse valor
- Compare o custo no ponto médio atual com o custo no ponto médio menos um para determinar a direção da pesquisa
- Continue estreitando o intervalo de pesquisa até encontrar a configuração de custo mínimo
// 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));
Saída
100
[Abordagem esperada - 2] Usando classificação - tempo O(n Log n) e espaço O(1)
A ideia é encontrar o valor ideal ao qual todos os elementos devem ser equalizados, que deve ser um dos elementos existentes do array. Classificando primeiro a matriz e depois iterando cada elemento como um valor alvo potencial, calculamos o custo de transformar todos os outros elementos nesse valor, rastreando de forma eficiente a soma dos elementos à esquerda e à direita da posição atual.
Abordagem passo a passo:
- Classifique a matriz para processar os elementos em ordem crescente.
- Para cada elemento como um valor alvo potencial, calcule dois custos: trazer elementos menores para cima e elementos maiores para baixo.
- Acompanhe as somas à esquerda e à direita para calcular esses custos de forma eficiente em tempo constante por iteração.
- Aumentando os custos dos elementos menores: (valor atual × número de elementos menores) - (soma dos elementos menores)
- Reduzindo os custos dos elementos maiores: (soma dos elementos maiores) - (valor atual × número de elementos maiores)
- Compare o custo atual com o custo mínimo.
// 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));
Saída
100Criar questionário