Dada una array que contiene valores enteros, necesitamos hacer que todos los valores de esta array sean iguales a algún valor entero con un costo mínimo donde el costo de cambiar un valor de array x a y es abs(xy).
Ejemplos:
Input : arr[] = [1, 100, 101] Output : 100 We can change all its values to 100 with minimum cost, |1 - 100| + |100 - 100| + |101 - 100| = 100 Input : arr[] = [4, 6] Output : 2 We can change all its values to 5 with minimum cost, |4 - 5| + |5 - 6| = 2
Este problema se puede resolver observando el costo mientras se cambia el valor igual objetivo, es decir, veremos el cambio en el costo cuando se cambia el valor igual objetivo. Se puede observar que, a medida que aumentamos el valor igual objetivo, el costo total disminuye hasta un límite y luego comienza a aumentar, es decir, el gráfico de costo con respecto al valor igual objetivo tiene forma de U y como el gráfico de costo tiene forma de U, la búsqueda ternaria se puede aplicar a este espacio de búsqueda y nuestro objetivo es obtener el punto más bajo de la curva que representará el menor costo. Haremos que el valor más pequeño y más grande de la array sea el límite de nuestro espacio de búsqueda y luego seguiremos saltando 1/3 parte del espacio de búsqueda hasta llegar al punto más bajo de nuestra curva en U.
Consulte el código a continuación para una mejor comprensión.
C++
// C++ program to find minimum cost to
// make all elements equal
#include <bits/stdc++.h>
using namespace std;
// Utility method to compute cost, when
// all values of array are made equal to X
int computeCost(int arr[], int N, int X)
{
int cost = 0;
for (int i = 0; i < N; i++)
cost += abs(arr[i] - X);
return cost;
}
// Method to find minimum cost to make all
// elements equal
int minCostToMakeElementEqual(int arr[], int N)
{
int low, high;
low = high = arr[0];
// setting limits for ternary search by
// smallest and largest element
for (int i = 0; i < N; i++) {
if (low > arr[i])
low = arr[i];
if (high < arr[i])
high = arr[i];
}
/* loop until difference between low and high
become less than 3, because after that
mid1 and mid2 will start repeating
*/
while ((high - low) > 2) {
// mid1 and mid2 are representative array
// equal values of search space
int mid1 = low + (high - low) / 3;
int mid2 = high - (high - low) / 3;
int cost1 = computeCost(arr, N, mid1);
int cost2 = computeCost(arr, N, mid2);
// if mid2 point gives more total cost,
// skip third part
if (cost1 < cost2)
high = mid2;
// if mid1 point gives more total cost,
// skip first part
else
low = mid1;
}
// computeCost gets optimum cost by sending
// average of low and high as X
return computeCost(arr, N, (low + high) / 2);
}
// Driver code to test above method
int main()
{
int arr[] = { 1, 100, 101 };
int N = sizeof(arr) / sizeof(int);
cout << minCostToMakeElementEqual(arr, N);
return 0;
}
Java
// JAVA Code for Make all array elements
// equal with minimum cost
class GFG {
// Utility method to compute cost, when
// all values of array are made equal to X
public static int computeCost(int arr[], int N,
int X)
{
int cost = 0;
for (int i = 0; i < N; i++)
cost += Math.abs(arr[i] - X);
return cost;
}
// Method to find minimum cost to make all
// elements equal
public static int minCostToMakeElementEqual(int arr[],
int N)
{
int low, high;
low = high = arr[0];
// setting limits for ternary search by
// smallest and largest element
for (int i = 0; i < N; i++) {
if (low > arr[i])
low = arr[i];
if (high < arr[i])
high = arr[i];
}
/* loop until difference between low and high
become less than 3, because after that
mid1 and mid2 will start repeating
*/
while ((high - low) > 2) {
// mid1 and mid2 are representative array
// equal values of search space
int mid1 = low + (high - low) / 3;
int mid2 = high - (high - low) / 3;
int cost1 = computeCost(arr, N, mid1);
int cost2 = computeCost(arr, N, mid2);
// if mid2 point gives more total cost,
// skip third part
if (cost1 < cost2)
high = mid2;
// if mid1 point gives more total cost,
// skip first part
else
low = mid1;
}
// computeCost gets optimum cost by sending
// average of low and high as X
return computeCost(arr, N, (low + high) / 2);
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = { 1, 100, 101 };
int N = arr.length;
System.out.println(minCostToMakeElementEqual(arr, N));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 program to find minimum # cost to make all elements equal # Utility method to compute cost, when # all values of array are made equal to X def computeCost(arr, N, X): cost = 0 for i in range(N): cost += abs(arr[i] - X) return cost # Method to find minimum cost to # make all elements equal def minCostToMakeElementEqual(arr, N): low = high = arr[0] # Setting limits for ternary search # by smallest and largest element for i in range(N): if (low > arr[i]): low = arr[i] if (high < arr[i]): high = arr[i] # loop until difference between low and # high become less than 3, because after # that mid1 and mid2 will start repeating while ((high - low) > 2): # mid1 and mid2 are representative # array equal values of search space mid1 = low + (high - low) // 3 mid2 = high - (high - low) // 3 cost1 = computeCost(arr, N, mid1) cost2 = computeCost(arr, N, mid2) # if mid2 point gives more total # cost, skip third part if (cost1 < cost2): high = mid2 # if mid1 point gives more total # cost, skip first part else: low = mid1 # computeCost gets optimum cost by # sending average of low and high as X return computeCost(arr, N, (low + high) // 2) # Driver code arr = [1, 100, 101] N = len(arr) print(minCostToMakeElementEqual(arr, N)) # This code is contributed by Anant Agarwal.
C#
// C# Code to Make all array elements
// equal with minimum cost
using System;
class GFG {
// Utility method to compute cost, when
// all values of array are made equal to X
public static int computeCost(int[] arr, int N,
int X)
{
int cost = 0;
for (int i = 0; i < N; i++)
cost += Math.Abs(arr[i] - X);
return cost;
}
// Method to find minimum cost to
// make all elements equal
public static int minCostToMakeElementEqual(int[] arr,
int N)
{
int low, high;
low = high = arr[0];
// setting limits for ternary search by
// smallest and largest element
for (int i = 0; i < N; i++) {
if (low > arr[i])
low = arr[i];
if (high < arr[i])
high = arr[i];
}
/* loop until difference between low and high
become less than 3, because after that
mid1 and mid2 will start repeating
*/
while ((high - low) > 2) {
// mid1 and mid2 are representative array
// equal values of search space
int mid1 = low + (high - low) / 3;
int mid2 = high - (high - low) / 3;
int cost1 = computeCost(arr, N, mid1);
int cost2 = computeCost(arr, N, mid2);
// if mid2 point gives more total cost,
// skip third part
if (cost1 < cost2)
high = mid2;
// if mid1 point gives more total cost,
// skip first part
else
low = mid1;
}
// computeCost gets optimum cost by sending
// average of low and high as X
return computeCost(arr, N, (low + high) / 2);
}
/* Driver program to test above function */
public static void Main()
{
int[] arr = { 1, 100, 101 };
int N = arr.Length;
Console.Write(minCostToMakeElementEqual(arr, N));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// PHP program to find minimum cost
// to make all elements equal
// Utility method to compute cost,
// when all values of array are
// made equal to X
function computeCost($arr, $N, $X)
{
$cost = 0;
for ($i = 0; $i < $N; $i++)
$cost += abs($arr[$i] - $X);
return $cost;
}
// Method to find minimum cost
// to make all elements equal
function minCostToMakeElementEqual($arr, $N)
{
$low; $high;
$low = $high = $arr[0];
// setting limits for ternary
// search by smallest and
// largest element
for ($i = 0; $i < $N; $i++)
{
if ($low > $arr[$i])
$low = $arr[$i];
if ($high < $arr[$i])
$high = $arr[$i];
}
/* loop until difference between
low and high become less than 3,
because after that mid1 and mid2
will start repeating */
while (($high - $low) > 2)
{
// mid1 and mid2 are representative
// array equal values of search space
$mid1 = $low + (floor($high - $low) / 3);
$mid2 = $high - ($high - $low) / 3;
$cost1 = computeCost($arr, $N, $mid1);
$cost2 = computeCost($arr, $N, $mid2);
// if mid2 point gives more total
// cost, skip third part
if ($cost1 < $cost2)
$high = $mid2;
// if mid1 point gives more
// total cost, skip first part
else
$low = $mid1;
}
// computeCost gets optimum cost by
// sending average of low and high as X
return computeCost($arr, $N, ($low +
$high) / 2);
}
// Driver Code
$arr = array( 1, 100, 101 );
$N = sizeof($arr) / sizeof($arr[0]);
echo minCostToMakeElementEqual($arr, $N);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript program to find minimum cost to
// make all elements equal
// Utility method to compute cost, when
// all values of array are made equal to X
function computeCost(arr, N, X)
{
let cost = 0;
for (let i = 0; i < N; i++)
cost += Math.abs(arr[i] - X);
return cost;
}
// Method to find minimum cost to make all
// elements equal
function minCostToMakeElementEqual(arr, N)
{
let low, high;
low = high = arr[0];
// setting limits for ternary search by
// smallest and largest element
for (let i = 0; i < N; i++) {
if (low > arr[i])
low = arr[i];
if (high < arr[i])
high = arr[i];
}
/* loop until difference between low and high
become less than 3, because after that
mid1 and mid2 will start repeating
*/
while ((high - low) > 2) {
// mid1 and mid2 are representative array
// equal values of search space
let mid1 = low + (high - low) / 3;
let mid2 = high - (high - low) / 3;
let cost1 = computeCost(arr, N, mid1);
let cost2 = computeCost(arr, N, mid2);
// if mid2 point gives more total cost,
// skip third part
if (cost1 < cost2)
high = mid2;
// if mid1 point gives more total cost,
// skip first part
else
low = mid1;
}
// computeCost gets optimum cost by sending
// average of low and high as X
return Math.round(computeCost(arr, N, (low + high) / 2));
}
// Driver Code
let arr = [ 1, 100, 101 ];
let N = arr.length;
document.write(minCostToMakeElementEqual(arr, N));
</script>
Producción:
100
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(1)
Solución alternativa
Piensa geométricamente. Suponga que los elementos de la array están coordinados en el eje x. El problema se reduce a encontrar otra coordenada tal que la suma de distancias entre esta elección y otras coordenadas se minimice.
Observe que: si el número de coordenadas es impar, entonces y = elemento central. Si incluso entonces y es cualquier número entre las 2 coordenadas centrales. Di Entrada = [a, b, c, d]. La salida es cualquier número entre b y c, incluidos ambos. Por lo tanto, el costo es una suma que se puede calcular fácilmente ahora que hemos elegido y. suma|(y-ai)| por todo yo
Es realmente fácil codificarlo.
C++
#include <bits/stdc++.h>
using namespace std;
// This function assumes that a[] is
// sorted. If a[] is not sorted, we need
// to sort it first.
int minCostToMakeElementEqual(int a[], int n)
{
// If there are odd elements, we choose
// middle element
int y;
if (n % 2 == 1)
y = a[n / 2];
// If there are even elements, then we choose
// the average of middle two.
else
y = (a[n / 2] + a[(n - 2) / 2]) / 2;
// After deciding the final value, find the
// result.
int s = 0;
for(int i = 0; i < n; i++)
s += abs(a[i] - y);
return s;
}
// Driver code
int main()
{
int a[] = { 1, 100, 101 };
int n = sizeof(a) / sizeof(a[0]);
cout << (minCostToMakeElementEqual(a, n));
}
// This code is contributed by chitranayal
Java
import java.io.*;
import java.util.*;
class GFG{
// This function assumes that a[] is
// sorted. If a[] is not sorted, we need
// to sort it first.
public static int minCostToMakeElementEqual(int a[],
int n)
{
// If there are odd elements, we choose
// middle element
int y;
if (n % 2 == 1)
y = a[n / 2];
// If there are even elements, then we
// choose the average of middle two.
else
y = (a[n / 2] + a[(n - 2) / 2]) / 2;
// After deciding the final value,
// find the result.
int s = 0;
for(int i = 0; i < n; i++)
s += Math.abs(a[i] - y);
return s;
}
// Driver code
public static void main (String[] args)
{
int a[] = { 1, 100, 101 };
int n = a.length;
System.out.println(minCostToMakeElementEqual(a, n));
}
}
// This code is contributed by parascoding
Python3
# This function assumes that a[] is # sorted. If a[] is not sorted, we need # to sort it first. def minCostToMakeElementEqual(a): l = len(a) # If there are odd elements, we choose # middle element if (l%2 == 1): y = a[l//2] # If there are even elements, then we choose # the average of middle two. else: y = (a[l//2] + a[(l-2)//2])//2 # After deciding the final value, find the # result. s = 0 for i in range(l): s += abs(a[i]-y) return s # Driver code a = [1, 100, 101] print(minCostToMakeElementEqual(a))
C#
using System;
using System.Collections.Generic;
class GFG{
// This function assumes that a[] is
// sorted. If a[] is not sorted, we need
// to sort it first.
static int minCostToMakeElementEqual(int[] a,
int n)
{
// If there are odd elements, we choose
// middle element
int y;
if (n % 2 == 1)
y = a[n / 2];
// If there are even elements, then we
// choose the average of middle two.
else
y = (a[n / 2] + a[(n - 2) / 2]) / 2;
// After deciding the final value,
// find the result.
int s = 0;
for(int i = 0; i < n; i++)
s += Math.Abs(a[i] - y);
return s;
}
// Driver code
static void Main()
{
int[] a = { 1, 100, 101 };
int n = a.Length;
Console.WriteLine(
minCostToMakeElementEqual(a, n));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// This function assumes that a[] is
// sorted. If a[] is not sorted, we need
// to sort it first.
function minCostToMakeElementEqual( a, n)
{
// If there are odd elements, we choose
// middle element
let y;
if (n % 2 == 1)
y = a[Math.trunc(n / 2)];
// If there are even elements, then we choose
// the average of middle two.
else
y = Math.trunc((a[n / 2] + a[(n - 2) / 2]) / 2);
// After deciding the final value, find the
// result.
let s = 0;
for(let i = 0; i < n; i++)
s += Math.abs(a[i] - y);
return s;
}
// Driver program
let a = [ 1, 100, 101 ];
let n = a.length;
document.write(minCostToMakeElementEqual(a, n));
</script>
Producción
100
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA