Incremento/decremento mínimo para hacer que los elementos de la array sean iguales

Dada una array de enteros donde $1 \leq A[i] \leq 10^{18}$ . En una operación, puede aumentar o disminuir cualquier elemento en 1. La tarea es encontrar las operaciones mínimas necesarias para realizar en los elementos de la array para hacer que todos los elementos de la array sean iguales.

Ejemplos :

Input : A[] = { 1, 5, 7, 10 }
Output : 11
Increment 1 by 4, 5 by 0.
Decrement 7 by 2, 10 by 5.
New array A = { 5, 5, 5, 5 } with 
cost of operations = 4 + 0 + 2 + 5 = 11.

Input : A = { 10, 2, 20 }
Output : 18

Acercarse:

Ordene la array de números enteros en orden creciente.
Ahora, para hacer que todos los elementos sean iguales con el costo mínimo. Tendremos que hacer que los elementos sean iguales al elemento central de esta array ordenada. Por lo tanto, seleccione el valor medio, sea K.
Nota : en el caso de un número par de elementos, tendremos que verificar los costos de ambos elementos medios y tomar el mínimo.
Si A[i] < K , incrementa el elemento en K – A[i] .
Si A[i] > K , Decrementa el elemento por A[i] – K .
Actualizar costo de cada operación realizada.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to find minimum Increment or
// decrement to make array elements equal
#include <bits/stdc++.h>
using namespace std;
 
// Function to return minimum operations need
// to be make each element of array equal
int minCost(int A[], int n)
{
    // Initialize cost to 0
    int cost = 0;
 
    // Sort the array
    sort(A, A + n);
 
    // Middle element
    int K = A[n / 2];
 
    // Find Cost
    for (int i = 0; i < n; ++i)
        cost += abs(A[i] - K);
 
    // If n, is even. Take minimum of the
    // Cost obtained by considering both
    // middle elements
    if (n % 2 == 0) {
        int tempCost = 0;
 
        K = A[(n / 2) - 1];
 
        // Find cost again
        for (int i = 0; i < n; ++i)
            tempCost += abs(A[i] - K);
 
        // Take minimum of two cost
        cost = min(cost, tempCost);
    }
 
    // Return total cost
    return cost;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 6, 7, 10 };
 
    int n = sizeof(A) / sizeof(A[0]);
 
    cout << minCost(A, n);
 
    return 0;
}

Java

// Java program to find minimum Increment or
// decrement to make array elements equal
import java.util.*;
class GfG {
 
// Function to return minimum operations need
// to be make each element of array equal
static int minCost(int A[], int n)
{
    // Initialize cost to 0
    int cost = 0;
 
    // Sort the array
    Arrays.sort(A);
 
    // Middle element
    int K = A[n / 2];
 
    // Find Cost
    for (int i = 0; i < n; ++i)
        cost += Math.abs(A[i] - K);
 
    // If n, is even. Take minimum of the
    // Cost obtained by considering both
    // middle elements
    if (n % 2 == 0) {
        int tempCost = 0;
 
        K = A[(n / 2) - 1];
 
        // Find cost again
        for (int i = 0; i < n; ++i)
            tempCost += Math.abs(A[i] - K);
 
        // Take minimum of two cost
        cost = Math.min(cost, tempCost);
    }
 
    // Return total cost
    return cost;
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 1, 6, 7, 10 };
 
    int n = A.length;
 
    System.out.println(minCost(A, n));
}
}

Python3

# Python3 program to find minimum Increment or
# decrement to make array elements equal
     
# Function to return minimum operations need
# to be make each element of array equal
def minCost(A, n):
     
    # Initialize cost to 0
    cost = 0
     
    # Sort the array
    A.sort();
     
    # Middle element
    K = A[int(n / 2)]
     
    #Find Cost
    for i in range(0, n):
        cost = cost + abs(A[i] - K)
     
    # If n, is even. Take minimum of the
    # Cost obtained by considering both
    # middle elements
    if n % 2 == 0:
        tempCost = 0
        K = A[int(n / 2) - 1]
         
        # FInd cost again
        for i in range(0, n):
            tempCost = tempCost + abs(A[i] - K)
         
        # Take minimum of two cost
        cost = min(cost, tempCost)
         
    # Return total cost
    return cost
     
# Driver code
A = [1, 6, 7, 10]
n = len(A)
 
print(minCost(A, n))
         
# This code is contributed
# by Shashank_Sharma

C#

// C# program to find minimum Increment or
// decrement to make array elements equal
using System;
 
class GFG {
     
// Function to return minimum operations need
// to be make each element of array equal
static int minCost(int []A, int n)
{
    // Initialize cost to 0
    int cost = 0;
 
    // Sort the array
    Array.Sort(A);
 
    // Middle element
    int K = A[n / 2];
 
    // Find Cost
    for (int i = 0; i < n; ++i)
        cost += Math.Abs(A[i] - K);
 
    // If n, is even. Take minimum of the
    // Cost obtained by considering both
    // middle elements
    if (n % 2 == 0) {
        int tempCost = 0;
 
        K = A[(n / 2) - 1];
 
        // Find cost again
        for (int i = 0; i < n; ++i)
            tempCost += Math.Abs(A[i] - K);
 
        // Take minimum of two cost
        cost = Math.Min(cost, tempCost);
    }
 
    // Return total cost
    return cost;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []A = new int []{ 1, 6, 7, 10 };
 
    int n = A.Length;
 
    Console.WriteLine(minCost(A, n));
}
}

PHP

<?php
// PHP program to find minimum Increment or
// decrement to make array elements equal
 
// Function to return minimum operations need
// to be make each element of array equal
function minCost($A, $n)
{
    // Initialize cost to 0
    $cost = 0;
 
    // Sort the array
    sort($A);
 
    // Middle element
    $K = $A[$n / 2];
    // Find Cost
    for ($i = 0; $i < $n; ++$i)
        $cost += abs($A[$i] - $K);
 
    // If n, is even. Take minimum of the
    // Cost obtained by considering both
    // middle elements
    if ($n % 2 == 0)
    {
        $tempCost = 0;
 
        $K = $A[($n / 2) - 1];
 
        // Find cost again
        for ($i = 0; $i < $n; ++$i)
            $tempCost += abs($A[$i] - $K);
 
        // Take minimum of two cost
        $cost = min($cost, $tempCost);
    }
 
    // Return total cost
    return $cost;
}
 
// Driver Code
$A = array( 1, 6, 7, 10 );
$n = sizeof($A);
echo minCost($A, $n);
 
// This code is contributed
// by Sach_Code
?>

Javascript

<script>
 
// Javascript program to find minimum Increment or
// decrement to make array elements equal
 
// Function to return minimum operations need
// to be make each element of array equal
function minCost(A,n)
{
    // Initialize cost to 0
    var cost = 0;
 
    // Sort the array
    A.sort();
 
    // Middle element
    var K = A[parseInt(n/2)];
    var i;
    // Find Cost
    for (i = 0; i < n; ++i)
        cost += Math.abs(A[i] - K);
     
 
    // If n, is even. Take minimum of the
    // Cost obtained by considering both
    // middle elements
    if (n % 2 == 0) {
        var tempCost = 0;
 
        K = A[parseInt(n / 2) - 1];
 
        // Find cost again
        for (i = 0; i < n; ++i)
            tempCost += Math.abs(A[i] - K);
 
        // Take minimum of two cost
        cost = Math.min(cost, tempCost);
    }
 
    // Return total cost
    return cost;
}
 
// Driver Code
    var A = [1, 6, 7, 10];
 
    var n = A.length;
    document.write(minCost(A, n));
 
</script>

Producción:

Complejidad de tiempo: O(N*log(N)), Espacio auxiliar: O(1)

Optimización adicional Podemos encontrar la mediana en tiempo lineal y reducir la complejidad del tiempo a O(N)

Publicación traducida automáticamente

Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta