Dada una array arr[] de enteros positivos y tres enteros A , R , M , donde
- El costo de agregar 1 a un elemento de la array es A ,
- el costo de restar 1 de un elemento de la array es R y
- el costo de sumar 1 a un elemento y restar 1 de otro elemento simultáneamente es M .
La tarea es encontrar el costo total mínimo para hacer que todos los elementos de la array sean iguales.
Ejemplos:
Entrada: arr[] = {5, 5, 3, 6, 5}, A = 1, R = 2, M = 4
Salida: 4
Explicación:
Operación 1: Añadir dos veces al elemento 3, Array – {5, 5 , 5, 6, 5}, Costo = 2
Operación 2: Resta una vez al elemento 6, Array – {5, 5, 5, 5, 5}, Costo = 4
Por lo tanto, el costo mínimo es 4.Entrada: arr[] = {5, 5, 3, 6, 5}, A = 1, R = 2, M = 2
Salida: 3
Enfoque: La idea es:
- encuentre el mínimo de M y A + R ya que M puede hacer ambas operaciones simultáneamente.
- Luego, almacene la suma de prefijos en una array para encontrar la suma en tiempo constante.
- Ahora, para cada elemento, calcule el costo de hacerlo igual al elemento actual y encuentre el mínimo de ellos.
- La respuesta más pequeña también puede existir cuando hacemos que todos los elementos sean iguales al promedio de la array.
- Por lo tanto, al final también calcule el costo de hacer que todos los elementos sean iguales a la suma promedio aproximada de elementos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum cost to make all array
// elements equal
#include <bits/stdc++.h>
using namespace std;
// Function that returns the cost of
// making all elements equal to current element
int costCalculation(
int current, int arr[],
int n, int pref[],
int a, int r,
int minimum)
{
// Compute the lower bound
// of current element
int index
= lower_bound(
arr, arr + n, current)
- arr;
// Calculate the requirement
// of add operation
int left
= index * current - pref[index];
// Calculate the requirement
// of subtract operation
int right
= pref[n] - pref[index]
- (n - index)
* current;
// Compute minimum of left and right
int res = min(left, right);
left -= res;
right -= res;
// Computing the total cost of add
// and subtract operations
int total = res * minimum;
total += left * a;
total += right * r;
return total;
}
// Function that prints minimum cost
// of making all elements equal
void solve(int arr[], int n,
int a, int r, int m)
{
// Sort the given array
sort(arr, arr + n);
// Calculate minimum from a + r and m
int minimum = min(a + r, m);
int pref[n + 1] = { 0 };
// Compute prefix sum
// and store in pref
// array
for (int i = 0; i < n; i++)
pref[i + 1] = pref[i] + arr[i];
int ans = 10000;
// Find the minimum cost
// from the given elements
for (int i = 0; i < n; i++)
ans
= min(
ans,
costCalculation(
arr[i], arr, n,
pref, a, r,
minimum));
// Finding the minimum cost
// from the other cases where
// minimum cost can occur
ans
= min(
ans,
costCalculation(
pref[n] / n, arr,
n, pref, a,
r, minimum));
ans
= min(
ans,
costCalculation(
pref[n] / n + 1,
arr, n, pref,
a, r, minimum));
// Printing the minimum cost of making
// all elements equal
cout << ans << "\n";
}
// Driver Code
int main()
{
int arr[] = { 5, 5, 3, 6, 5 };
int A = 1, R = 2, M = 4;
int size = sizeof(arr) / sizeof(arr[0]);
// Function Call
solve(arr, size, A, R, M);
return 0;
}
Java
// Java implementation to find the
// minimum cost to make all array
// elements equal
import java.lang.*;
import java.util.*;
class GFG{
public static int lowerBound(int[] array, int length,
int value)
{
int low = 0;
int high = length;
while (low < high)
{
final int mid = (low + high) / 2;
// Checks if the value is less
// than middle element of the array
if (value <= array[mid])
{
high = mid;
}
else
{
low = mid + 1;
}
}
return low;
}
// Function that returns the cost of making
// all elements equal to current element
public static int costCalculation(int current, int arr[],
int n, int pref[],
int a, int r,
int minimum)
{
// Compute the lower bound
// of current element
int index = lowerBound(arr, arr.length, current);
// Calculate the requirement
// of add operation
int left = index * current - pref[index];
// Calculate the requirement
// of subtract operation
int right = pref[n] -
pref[index]- (n - index)* current;
// Compute minimum of left and right
int res = Math.min(left, right);
left -= res;
right -= res;
// Computing the total cost of add
// and subtract operations
int total = res * minimum;
total += left * a;
total += right * r;
return total;
}
// Function that prints minimum cost
// of making all elements equal
public static void solve(int arr[], int n,
int a, int r, int m)
{
// Sort the given array
Arrays.sort(arr);
// Calculate minimum from a + r and m
int minimum = Math.min(a + r, m);
int []pref = new int [n + 1];
Arrays.fill(pref, 0);
// Compute prefix sum and
// store in pref array
for(int i = 0; i < n; i++)
pref[i + 1] = pref[i] + arr[i];
int ans = 10000;
// Find the minimum cost
// from the given elements
for(int i = 0; i < n; i++)
ans = Math.min(ans, costCalculation(arr[i], arr,
n, pref,
a, r, minimum));
// Finding the minimum cost
// from the other cases where
// minimum cost can occur
ans = Math.min(ans, costCalculation(pref[n] / n, arr,
n, pref, a, r,
minimum));
ans = Math.min(ans, costCalculation(pref[n] / n + 1,
arr, n, pref,
a, r, minimum));
// Printing the minimum cost of making
// all elements equal
System.out.println(ans);
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 5, 5, 3, 6, 5 };
int A = 1, R = 2, M = 4;
int size = arr.length ;
// Function Call
solve(arr, size, A, R, M);
}
}
// This code is contributed by SoumikMondal
Python3
# Python3 implementation to find the # minimum cost to make all array # elements equal def lowerBound(array, length, value): low = 0 high = length while (low < high): mid = (low + high) // 2 # Checks if the value is less # than middle element of the array if (value <= array[mid]): high = mid else: low = mid + 1 return low # Function that returns the cost of making # all elements equal to current element def costCalculation(current, arr, n, pref, a, r, minimum): # Compute the lower bound # of current element index = lowerBound(arr, len(arr), current) # Calculate the requirement # of add operation left = index * current - pref[index] # Calculate the requirement # of subtract operation right = (pref[n] - pref[index] - (n - index) * current) # Compute minimum of left and right res = min(left, right) left -= res right -= res # Computing the total cost of add # and subtract operations total = res * minimum total += left * a total += right * r return total # Function that prints minimum cost # of making all elements equal def solve(arr, n, a, r, m): # Sort the given array arr.sort() # Calculate minimum from a + r and m minimum = min(a + r, m) pref = [0] * (n + 1) # Compute prefix sum and # store in pref array for i in range(n): pref[i + 1] = pref[i] + arr[i] ans = 10000 # Find the minimum cost # from the given elements for i in range(n): ans = min(ans, costCalculation(arr[i], arr, n, pref, a, r, minimum)) # Finding the minimum cost # from the other cases where # minimum cost can occur ans = min(ans, costCalculation(pref[n] // n, arr, n, pref, a, r, minimum)) ans = min(ans, costCalculation(pref[n] // n + 1, arr, n, pref, a, r, minimum)) # Printing the minimum cost of making # all elements equal print(ans) # Driver Code if __name__ == "__main__": arr = [ 5, 5, 3, 6, 5 ] A = 1 R = 2 M = 4 size = len(arr) # Function call solve(arr, size, A, R, M) # This code is contributed by chitranayal
C#
// C# implementation to find the
// minimum cost to make all array
// elements equal
using System;
class GFG{
public static int lowerBound(int[] array,
int length,
int value)
{
int low = 0;
int high = length;
while (low < high)
{
int mid = (low + high) / 2;
// Checks if the value is less
// than middle element of the array
if (value <= array[mid])
{
high = mid;
}
else
{
low = mid + 1;
}
}
return low;
}
// Function that returns the cost of making
// all elements equal to current element
public static int costCalculation(int current,
int []arr, int n,
int []pref, int a,
int r, int minimum)
{
// Compute the lower bound
// of current element
int index = lowerBound(arr, arr.Length, current);
// Calculate the requirement
// of add operation
int left = index * current - pref[index];
// Calculate the requirement
// of subtract operation
int right = pref[n] - pref[index] -
(n - index) *
current;
// Compute minimum of left and right
int res = Math.Min(left, right);
left -= res;
right -= res;
// Computing the total cost of add
// and subtract operations
int total = res * minimum;
total += left * a;
total += right * r;
return total;
}
// Function that prints minimum cost
// of making all elements equal
public static void solve(int []arr, int n,
int a, int r, int m)
{
// Sort the given array
Array.Sort(arr);
// Calculate minimum from a + r and m
int minimum = Math.Min(a + r, m);
int []pref = new int [n + 1];
Array.Fill(pref, 0);
// Compute prefix sum and
// store in pref array
for(int i = 0; i < n; i++)
pref[i + 1] = pref[i] + arr[i];
int ans = 10000;
// Find the minimum cost
// from the given elements
for(int i = 0; i < n; i++)
ans = Math.Min(ans, costCalculation(arr[i], arr,
n, pref, a,
r, minimum));
// Finding the minimum cost
// from the other cases where
// minimum cost can occur
ans = Math.Min(ans, costCalculation(pref[n] / n, arr,
n, pref, a, r,
minimum));
ans = Math.Min(ans, costCalculation(pref[n] / n + 1,
arr, n, pref,
a, r, minimum));
// Printing the minimum cost of making
// all elements equal
Console.WriteLine(ans);
}
// Driver Code
public static void Main(string []args)
{
int []arr = { 5, 5, 3, 6, 5 };
int A = 1, R = 2, M = 4;
int size = arr.Length ;
// Function Call
solve(arr, size, A, R, M);
}
}
// This code is contributed by SoumikMondal
Javascript
<script>
// javascript implementation to find the
// minimum cost to make all array
// elements equal
function lowerBound(array, length, value)
{
var low = 0;
var high = length;
while (low < high)
{
var mid = parseInt((low + high) / 2);
// Checks if the value is less
// than middle element of the array
if (value <= array[mid])
{
high = mid;
}
else
{
low = mid + 1;
}
}
return low;
}
// Function that returns the cost of making
// all elements equal to current element
function costCalculation(current , arr , n , pref , a , r , minimum)
{
// Compute the lower bound
// of current element
var index = lowerBound(arr, arr.length, current);
// Calculate the requirement
// of add operation
var left = index * current - pref[index];
// Calculate the requirement
// of subtract operation
var right = pref[n] - pref[index] - (n - index) * current;
// Compute minimum of left and right
var res = Math.min(left, right);
left -= res;
right -= res;
// Computing the total cost of add
// and subtract operations
var total = res * minimum;
total += left * a;
total += right * r;
return total;
}
// Function that prints minimum cost
// of making all elements equal
function solve(arr , n , a , r , m) {
// Sort the given array
arr.sort();
// Calculate minimum from a + r and m
var minimum = Math.min(a + r, m);
var pref = Array(n+1).fill(0);
// Compute prefix sum and
// store in pref array
for (i = 0; i < n; i++)
pref[i + 1] = pref[i] + arr[i];
var ans = 10000;
// Find the minimum cost
// from the given elements
for (i = 0; i < n; i++)
ans = Math.min(ans, costCalculation(arr[i], arr, n, pref, a, r, minimum));
// Finding the minimum cost
// from the other cases where
// minimum cost can occur
ans = Math.min(ans, costCalculation(pref[n] / n, arr, n, pref, a, r, minimum));
ans = Math.min(ans, costCalculation(pref[n] / n + 1, arr, n, pref, a, r, minimum));
// Printing the minimum cost of making
// all elements equal
document.write(ans);
}
// Driver Code
var arr = [ 5, 5, 3, 6, 5 ];
var A = 1, R = 2, M = 4;
var size = arr.length;
// Function Call
solve(arr, size, A, R, M);
// This code is contributed by Rajput-Ji.
</script>
Producción:
4
Complejidad de tiempo: O(n log n), usado para clasificar
Espacio auxiliar: O(n), ya que se usa espacio adicional de tamaño n para crear una array de prefijos
Publicación traducida automáticamente
Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA