Dada una array ordenada arr[] de tamaño N (1 ≤ N ≤ 10 5 ) y dos números enteros A y B, la tarea es calcular el costo mínimo requerido para hacer que todos los elementos de la array sean iguales por incrementos o decrementos. El costo de cada incremento y decremento son A y B respectivamente.
Ejemplos:
Entrada: arr[] = { 2, 5, 6, 9, 10, 12, 15 }, A = 1, B = 2
Salida: 32
Explicación:
Incrementar arr[0] en 8, arr[1] en 5, arr [2] por 4, arr[3] por 1, arr[4] por 0. Decrementa arr[5] por 2, arr[6] por 5.
Por lo tanto, arr[] se modifica a { 10, 10, 10, 10 , 10, 10, 10 }.
Por lo tanto, costo total requerido = (8 + 5 + 4 + 1 + 0) * 1 + (2 + 5) * 2 = 18 + 14 = 32Entrada: arr[] = { 2, 3, 4 }, A = 10, B = 1
Salida: 3
Enfoque: Siga los pasos debajo de la implementación:
- Ordene la array en orden ascendente .
- Atraviesa la array .
- Inicialice una nueva array para almacenar la suma acumulativa de prefijos .
- Si A y B son iguales, entonces el elemento medio tendrá el costo mínimo.
- Si A es menor que B , entonces el elemento de costo mínimo está presente en el lado derecho de mid al establecer low = mid + 1 . Busque ese elemento utilizando la técnica de búsqueda binaria .
- Si A es mayor que B , entonces el elemento de costo mínimo está presente en el lado izquierdo de mid . Busque ese elemento utilizando la técnica de búsqueda binaria configurando high = mid – 1 .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum cost
// required to make all array elements equal
long long minCost(int arr[], int A,
int B, int N)
{
// Sort the array
sort(arr, arr + N);
// Stores the prefix sum and sum
// of the array respectively
long long cumarr[N], sum = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update sum
sum += arr[i];
// Update prefix sum
cumarr[i] = sum;
}
// Update middle element
int mid = (N - 1) / 2;
// Calculate cost to convert
// every element to mid element
long long ans
= (arr[mid] * (mid + 1)
- cumarr[mid])
* A
+ (cumarr[N - 1] - cumarr[mid]
- (arr[mid] * (N - 1 - mid)))
* B;
if (A == B)
return ans;
else if (A < B) {
int low = mid, high = N - 1;
// Binary search
while (low <= high) {
mid = low + (high - low) / 2;
long long curr
= (arr[mid] * (mid + 1)
- cumarr[mid])
* A
+ (cumarr[N - 1] - cumarr[mid]
- (arr[mid] * (N - 1 - mid)))
* B;
if (curr <= ans) {
ans = curr;
low = mid + 1;
}
else
high = mid - 1;
}
return ans;
}
else {
int low = 0, high = mid;
// Binary search
while (low <= high) {
mid = low + (high - low) / 2;
long long curr
= (arr[mid] * (mid + 1)
- cumarr[mid])
* A
+ (cumarr[N - 1] - cumarr[mid]
- (arr[mid] * (N - 1 - mid)))
* B;
if (curr <= ans) {
ans = curr;
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
}
// Driver Code
int main()
{
int arr[] = { 2, 5, 6, 9, 10, 12, 15 };
int A = 1, B = 2;
int N = sizeof(arr) / sizeof(arr[0]);
cout << minCost(arr, A, B, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to find minimum cost required
// to make all array elements equal
static int minCost(int[] arr, int A,
int B, int N)
{
// Sort the array
Arrays.sort(arr);
// Stores the prefix sum and sum
// of the array respectively
int[] cumarr = new int[N];
int sum = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update sum
sum += arr[i];
// Update prefix sum
cumarr[i] = sum;
}
// Update middle element
int mid = (N - 1) / 2;
// Calculate cost to convert
// every element to mid element
int ans = (arr[mid] * (mid + 1) - cumarr[mid]) *
A + (cumarr[N - 1] -
cumarr[mid] - (arr[mid] * (N -
1 - mid))) * B;
if (A == B)
return ans;
else if (A < B)
{
int low = mid, high = N - 1;
// Binary search
while (low <= high)
{
mid = low + (high - low) / 2;
int curr = (arr[mid] * (mid + 1) -
cumarr[mid]) * A + (cumarr[N - 1] -
cumarr[mid] - (arr[mid] *
(N - 1 - mid))) * B;
if (curr <= ans)
{
ans = curr;
low = mid + 1;
}
else
high = mid - 1;
}
return ans;
}
else
{
int low = 0, high = mid;
// Binary search
while (low <= high)
{
mid = low + (high - low) / 2;
int curr = (arr[mid] * (mid + 1) -
cumarr[mid]) * A + (cumarr[N - 1] -
cumarr[mid] - (arr[mid] * (N - 1 -
mid))) * B;
if (curr <= ans)
{
ans = curr;
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 5, 6, 9, 10, 12, 15 };
int A = 1, B = 2;
int N = (int)(arr.length);
System.out.println(minCost(arr, A, B, N));
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python program to implement # the above approach # Function to find minimum cost required # to make all array elements equal def minCost(arr, A, B, N): # Sort the array arr.sort(); # Stores the prefix sum and sum # of the array respectively cumarr = [0]*N; sum = 0; # Traverse the array for i in range(N): # Update sum sum += arr[i]; # Update prefix sum cumarr[i] = sum; # Update middle element mid = (N - 1) // 2; # Calculate cost to convert # every element to mid element ans = (arr[mid] * (mid + 1) - cumarr[mid]) * A\ + (cumarr[N - 1] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (A == B): return ans; elif (A < B): low = mid; high = N - 1; # Binary search while (low <= high): mid = low + (high - low) // 2; curr = (arr[mid] * (mid + 1) - cumarr[mid]) * A\ + (cumarr[N - 1] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (curr <= ans): ans = curr; low = mid + 1; else: high = mid - 1; return ans; else: low = 0; high = mid; # Binary search while (low <= high): mid = low + (high - low) // 2; curr = (arr[mid] * (mid + 1) - cumarr[mid]) * A\ + (cumarr[N - 1] - cumarr[mid] - (arr[mid] * (N - 1 - mid))) * B; if (curr <= ans): ans = curr; high = mid - 1; else: low = mid + 1; return ans; # Driver Code if __name__ == '__main__': arr = [2, 5, 6, 9, 10, 12, 15]; A = 1; B = 2; N = (int)(len(arr)); print(minCost(arr, A, B, N)); # This code is contributed by 29AjayKumar
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find minimum cost
// required to make all array elements equal
static ulong minCost(ulong[] arr, ulong A, ulong B,
ulong N)
{
// Sort the array
Array.Sort(arr);
// Stores the prefix sum and sum
// of the array respectively
ulong[] cumarr = new ulong[N];
ulong sum = 0;
// Traverse the array
for (ulong i = 0; i < N; i++)
{
// Update sum
sum += arr[i];
// Update prefix sum
cumarr[i] = sum;
}
// Update middle element
ulong mid = (N - 1) / 2;
// Calculate cost to convert
// every element to mid element
ulong ans = (arr[mid] * (mid + 1) - cumarr[mid]) * A
+ (cumarr[N - 1] - cumarr[mid]
- (arr[mid] * (N - 1 - mid)))
* B;
if (A == B)
return ans;
else if (A < B) {
ulong low = mid, high = N - 1;
// Binary search
while (low <= high) {
mid = low + (high - low) / 2;
ulong curr
= (arr[mid] * (mid + 1) - cumarr[mid])
* A
+ (cumarr[N - 1] - cumarr[mid]
- (arr[mid] * (N - 1 - mid)))
* B;
if (curr <= ans) {
ans = curr;
low = mid + 1;
}
else
high = mid - 1;
}
return ans;
}
else {
ulong low = 0, high = mid;
// Binary search
while (low <= high) {
mid = low + (high - low) / 2;
ulong curr
= (arr[mid] * (mid + 1) - cumarr[mid])
* A
+ (cumarr[N - 1] - cumarr[mid]
- (arr[mid] * (N - 1 - mid)))
* B;
if (curr <= ans) {
ans = curr;
high = mid - 1;
}
else
low = mid + 1;
}
return ans;
}
}
// Driver Code
public static void Main()
{
ulong[] arr = { 2, 5, 6, 9, 10, 12, 15 };
ulong A = 1, B = 2;
ulong N = (ulong)(arr.Length);
Console.Write(minCost(arr, A, B, N));
}
}
// This code is contributed by subhammahato348
Javascript
<script>
// Javascript program to implement
// the above approach
// Creating the bblSort function
function bblSort(arr){
for(var i = 0; i < arr.length; i++){
// Last i elements are already in place
for(var j = 0; j < ( arr.length - i -1 ); j++){
// Checking if the item at present iteration
// is greater than the next iteration
if(arr[j] > arr[j+1]){
// If the condition is true then swap them
var temp = arr[j]
arr[j] = arr[j + 1]
arr[j+1] = temp
}
}
}
return arr;
}
// Function to find minimum cost required
// to make all array elements equal
function minCost(arr , A , B , N) {
// Sort the array
arr = bblSort(arr);
// Stores the prefix sum and sum
// of the array respectively
var cumarr = Array(N).fill(0);
var sum = 0;
// Traverse the array
for (i = 0; i < N; i++) {
// Update sum
sum += arr[i];
// Update prefix sum
cumarr[i] = sum;
}
// Update middle element
var mid = ((N - 1) / 2);
// Calculate cost to convert
// every element to mid element
var ans = (arr[mid] * (mid + 1) - cumarr[mid]) * A
+ (cumarr[N - 1] - cumarr[mid] - (arr[mid] *
(N - 1 - mid))) * B-2;
if (A == B)
return ans;
else if (A < B) {
var low = mid, high = N - 1;
// Binary search
while (low <= high) {
mid = low + (high - low) / 2;
var curr = (arr[mid] * (mid + 1) - cumarr[mid]) * A
+ (cumarr[N - 2] - cumarr[mid] - (arr[mid] *
(N - 1 - mid))) * B;
if (curr <= ans) {
ans = curr;
low = mid + 1;
} else
high = mid - 1;
}
return ans;
}
else {
var low = 0, high = mid;
// Binary search
while (low <= high) {
mid = low + ((high - low) / 2);
var curr = (arr[mid] * (mid + 1) - cumarr[mid]) * A
+ (cumarr[N - 1] - cumarr[mid] - (arr[mid] *
(N - 1 - mid))) * B;
if (curr <= ans) {
ans = curr;
high = mid - 1;
} else
low = mid + 1;
}
return ans;
}
}
// Driver Code
var arr = [ 2, 5, 6, 9, 10, 12, 15 ];
var A = 1, B = 2;
var N = parseInt(arr.length);
document.write(minCost(arr, A, B, N));
// This code contributed by umadevi9616
</script>
Producción:
32
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por subhammahato348 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA