Dada una array arr[] de tamaño N y un entero K . La tarea es encontrar el costo mínimo requerido para recolectar la suma de la array. La suma de la array se recopila seleccionando cualquier elemento y agregándolo a un elemento de cualquier índice de la array. La adición de elementos con el mismo índice se permite como máximo K veces.
Ejemplo:
Entrada: arr[] = {3, 6, 4, 1, 1}, N = 5, K = 2
Salida: 11
Explicación: La suma de la array se puede recopilar de la siguiente manera:
- Elija el elemento en el índice 4 y agréguelo al elemento en el índice 2, es decir (1 ⇢ 4) = 1+4 = 5, cost = 1 y arr[] = {3, 6, 5, 1, 0}.
- Elija el elemento en el índice 3 y agréguelo al elemento en el índice 2, es decir (1 ⇢ 5) = 1+5 = 6, cost = 1+1 = 2 y arr[] = {3, 6, 6, 0, 0}.
- Elija el elemento en el índice 0 y agréguelo al elemento en el índice 1, es decir (3 ⇢ 6) = 3+6 = 9, costo = 2+3 = 5 y arr[] = {0, 9, 6, 0, 0}.
- Elija el elemento en el índice 2 y agréguelo al elemento en el índice 1, es decir (6 ⇢ 9) = 6+9 = 15, cost = 5+6 = 11 y arr[] = {0, 15, 0, 0, 0}.
Entrada: arr[] = {5, 3, 2, 1, 4, 6}, N = 6, K = 3
Salida: 18
Explicación: La suma se puede recopilar de la siguiente manera
- Elija el elemento en el índice 3 y agréguelo al elemento en el índice 4, es decir (1 ⇢ 4) = 1+4 = 5, cost = 1 y arr[] = {5, 3, 2, 0, 5, 6}.
- Elija el elemento en el índice 2 y agréguelo al elemento en el índice 0, es decir, (2 ⇢ 5) = 2+5 = 7, cost = 1+2 = 3 y arr[] = {7, 3, 0, 0, 5, 6 }.
- Elija el elemento en el índice 1 y agréguelo al elemento en el índice 5, es decir (3 ⇢ 6) = 3+6 = 9, cost = 3+3 = 6 y arr[] = {7, 0, 0, 0, 5, 9 }.
- Elija el elemento en el índice 4 y agréguelo al elemento en el índice 5, es decir (5 ⇢ 9) = 5+9 = 14, cost = 6+5 = 11 y arr[] = {7, 0, 0, 0, 0, 14 }.
- Elija el elemento en el índice 0 y agréguelo al elemento en el índice 5, es decir (7 ⇢ 14) = 7+14 = 21, cost = 11+7 = 18 y arr[] = {0, 0, 0, 0, 0, 21 }.
Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso . La idea es ordenar la array . siguiente interpretación del problema: los elementos dados son los vértices del grafo. Operación ⇢ añadir un elemento a otro ⇢ cambia a operación de suspensión de subárbol de un vértice a otro.
La tarea es obtener una configuración de árbol tal, que cada vértice no tenga más de K subárboles suspendidos, y la suma de los productos de los números, escritos en los vértices, y la profundidad de los vértices (donde la profundidad de la raíz es 0) sea mínima. Para minimizar la suma:
- los vértices con un número mayor no deben tener más profundidad que los vértices con un número menor (de lo contrario, es posible cambiarlos y obtener una suma menor).
- cada uno de los vértices interiores, además de, quizás, uno, tiene exactamente k sucesores. (En la implementación real, no hay necesidad de construir un árbol, solo necesitamos saber que se trata de un árbol).
Ahora calcule la suma para esta configuración. Para hacerlo, siga los siguientes pasos:
- Agregue a la respuesta la suma de los elementos del 1 al k-ésimo (en una array indexada en 0, ordenada en orden no creciente), multiplicada por 1 ; luego la suma de los tamaños de los siguientes k montones, multiplicada por 2; y así sucesivamente hasta el final de la array.
- Para obtener la respuesta sobre la suma del segmento, use la suma del prefijo después de ordenar la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the difference
// of the elements in a range
int sum(int s[], int l, int r, int N)
{
r = min(r, (N - 1));
return s[r] - s[l - 1];
}
// Function to find the minimum cost required
// to collect the sum of the array
int minCost(int arr[], int K, int N)
{
int s[N];
// Sort the array in descending order
sort(arr, arr + N, greater<int>());
s[0] = arr[0];
// Traverse and store the sums
// in prefix array s[]
for (int i = 1; i < N; i++)
s[i] = s[i - 1] + arr[i];
int res_1 = 0;
// Iterate the array and add the
// value of the element
// multiplied by its index
for (int i = 1; i < N; i++)
res_1 += arr[i] * i;
// If K = 1 return res_1
if (K == 1)
return res_1;
// Variable to store the answer
int res = 0, sz = 1;
// Traverse and find the
// answer accordingly
for (int j = 1, t = 1; j < N; j += sz, t++) {
sz *= K;
res += sum(s, j, j + sz - 1, N) * t;
}
// Return res
return res;
}
// Driver Code
int main()
{
// Initialize the array
int arr[] = { 3, 6, 4, 1, 1 };
int K = 2;
int N = sizeof(arr) / sizeof(arr[0]);
// Call the function and
// print the answer
cout << minCost(arr, K, N);
return 0;
}
Java
// Java code for the above approach
import java.util.Arrays;
import java.util.Collections;
class GFG {
// Function to return the difference
// of the elements in a range
static int sum(int s[], int l, int r, int N)
{
r = Math.min(r, (N - 1));
return s[r] - s[l - 1];
}
// Function to find the minimum cost required
// to collect the sum of the array
static int minCost(int arr[], int K, int N)
{
int[] s = new int[N];
// Sort the array in descending order
// Sorting the array in ascending order
Arrays.sort(arr);
// Reversing the array
reverse(arr);
s[0] = arr[0];
// Traverse and store the sums
// in prefix array s[]
for (int i = 1; i < N; i++)
s[i] = s[i - 1] + arr[i];
int res_1 = 0;
// Iterate the array and add the
// value of the element
// multiplied by its index
for (int i = 1; i < N; i++)
res_1 += arr[i] * i;
// If K = 1 return res_1
if (K == 1)
return res_1;
// Variable to store the answer
int res = 0, sz = 1;
// Traverse and find the
// answer accordingly
for (int j = 1, t = 1; j < N; j += sz, t++) {
sz *= K;
res += sum(s, j, j + sz - 1, N) * t;
}
// Return res
return res;
}
public static void reverse(int[] array)
{
// Length of the array
int n = array.length;
// Swaping the first half elements with last half
// elements
for (int i = 0; i < n / 2; i++) {
// Storing the first half elements temporarily
int temp = array[i];
// Assigning the first half to the last half
array[i] = array[n - i - 1];
// Assigning the last half to the first half
array[n - i - 1] = temp;
}
}
// Driver Code
public static void main(String[] args)
{
// Initialize the array
int arr[] = { 3, 6, 4, 1, 1 };
int K = 2;
int N = arr.length;
// Call the function and
// print the answer
System.out.println(minCost(arr, K, N));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python implementation for the above approach # Function to return the difference # of the elements in a range def sum (s, l, r, N): r = min(r, (N - 1)) return s[r] - s[l - 1] # Function to find the minimum cost required # to collect the sum of the array def minCost (arr, K, N): s = [0] * N # Sort the array in descending order arr = sorted(arr, reverse=True) s[0] = arr[0] # Traverse and store the sums # in prefix array s[] for i in range(1, N): s[i] = s[i - 1] + arr[i] res_1 = 0 # Iterate the array and add the # value of the element # multiplied by its index for i in range(1, N): res_1 += arr[i] * i # If K = 1 return res_1 if (K == 1): return res_1 # Variable to store the answer res = 0 sz = 1 # Traverse and find the # answer accordingly j=1 t=1 while(j < N ): sz *= K res += sum(s, j, j + sz - 1, N) * t j += sz t += 1 # Return res return res # Driver Code # Initialize the array arr = [3, 6, 4, 1, 1] K = 2 N = len(arr) # Call the function and # print the answer print(minCost(arr, K, N)) # This code is contributed by Saurabh Jaiswal
C#
// C# code for the above approach
using System;
public class GFG {
// Function to return the difference
// of the elements in a range
static int sum(int []s, int l, int r, int N)
{
r = Math.Min(r, (N - 1));
return s[r] - s[l - 1];
}
// Function to find the minimum cost required
// to collect the sum of the array
static int minCost(int []arr, int K, int N)
{
int[] s = new int[N];
// Sort the array in descending order
// Sorting the array in ascending order
Array.Sort(arr);
// Reversing the array
reverse(arr);
s[0] = arr[0];
// Traverse and store the sums
// in prefix array s[]
for (int i = 1; i < N; i++)
s[i] = s[i - 1] + arr[i];
int res_1 = 0;
// Iterate the array and add the
// value of the element
// multiplied by its index
for (int i = 1; i < N; i++)
res_1 += arr[i] * i;
// If K = 1 return res_1
if (K == 1)
return res_1;
// Variable to store the answer
int res = 0, sz = 1;
// Traverse and find the
// answer accordingly
for (int j = 1, t = 1; j < N; j += sz, t++) {
sz *= K;
res += sum(s, j, j + sz - 1, N) * t;
}
// Return res
return res;
}
public static void reverse(int[] array)
{
// Length of the array
int n = array.Length;
// Swaping the first half elements with last half
// elements
for (int i = 0; i < n / 2; i++) {
// Storing the first half elements temporarily
int temp = array[i];
// Assigning the first half to the last half
array[i] = array[n - i - 1];
// Assigning the last half to the first half
array[n - i - 1] = temp;
}
}
// Driver Code
public static void Main(String[] args)
{
// Initialize the array
int []arr = { 3, 6, 4, 1, 1 };
int K = 2;
int N = arr.Length;
// Call the function and
// print the answer
Console.WriteLine(minCost(arr, K, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation for the above approach
// Function to return the difference
// of the elements in a range
const sum = (s, l, r, N) => {
r = Math.min(r, (N - 1));
return s[r] - s[l - 1];
}
// Function to find the minimum cost required
// to collect the sum of the array
const minCost = (arr, K, N) => {
let s = new Array(N).fill(0);
// Sort the array in descending order
arr.sort((a, b) => b - a);
s[0] = arr[0];
// Traverse and store the sums
// in prefix array s[]
for (let i = 1; i < N; i++)
s[i] = s[i - 1] + arr[i];
let res_1 = 0;
// Iterate the array and add the
// value of the element
// multiplied by its index
for (let i = 1; i < N; i++)
res_1 += arr[i] * i;
// If K = 1 return res_1
if (K == 1)
return res_1;
// Variable to store the answer
let res = 0, sz = 1;
// Traverse and find the
// answer accordingly
for (let j = 1, t = 1; j < N; j += sz, t++) {
sz *= K;
res += sum(s, j, j + sz - 1, N) * t;
}
// Return res
return res;
}
// Driver Code
// Initialize the array
let arr = [3, 6, 4, 1, 1];
let K = 2;
let N = arr.length
// Call the function and
// print the answer
document.write(minCost(arr, K, N));
// This code is contributed by rakeshsahni
</script>
Producción
11
Complejidad de tiempo: O(N* log N)
Espacio auxiliar: O(N)