Dada una array arr[] que consta de N enteros, la tarea es encontrar el costo de eliminar todos los elementos de la array después de realizar las siguientes operaciones en el orden especificado cualquier cantidad de veces:
- Agregue el elemento máximo presente en la array dada al costo.
- Elimina el elemento máximo de la array dada.
- Disminuye todos los enteros en la array dada en 1 .
- Eliminar los elementos reducidos a 0.
Ejemplos:
Entrada: arr[] = {1, 6, 7, 4, 2, 5, 3}
Salida: 16
Explicación:
Paso 1: Elemento máximo actual = 7. Eliminar 7 y reducir cada elemento en 1 modifica la array a {0, 5, 3, 1, 4, 2}. Costo = 7.
Paso 2: Elemento máximo actual = 5. Eliminar 5 y reducir cada elemento en 1 modifica la array a {2, 0, 3, 1}. Costo = 7 + 5 = 12.
Paso 3: Máximo actual = 3. Eliminar 3 y reducir cada elemento en 1 modifica la array a {1, 1}. Costo = 12 + 3 = 15
Paso 4: Costo final obtenido = 15 + 1 = 16Entrada: arr[] = {6, 4, 6, 1}
Salida: 13
Enfoque ingenuo: el enfoque más simple para resolver el problema es el siguiente:
- Encuentre el máximo de la array dada
- Agréguelo al costo después de eliminarlo de la array.
- Una vez que se elimine el elemento máximo, reduzca todos los elementos restantes de la array en 1. Elimine todos los elementos reduciéndolos a 0.
- Repita los pasos anteriores hasta que se eliminen todos los elementos de la array.
- Finalmente, imprima el valor del costo .
Complejidad de tiempo: O(N 2 ), donde N es el tamaño de la array dada.
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es observar que cada i -ésimo elemento más grande de la array se agrega arr[i] – i veces al costo, donde i es el índice de cada elemento arr[i] . Siga los pasos a continuación para resolver el problema anterior:
- Ordena la array dada en orden decreciente .
- Recorra la array y agregue el valor arr[i] – i para que cada elemento de la array cueste si es mayor que 0 .
- Una vez completados los pasos anteriores, imprima el valor del costo .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the total cost
// of removing all array elements
int findCost(int* a, int n)
{
// Sort the array in descending order
sort(a, a + n, greater<int>());
// Stores the total cost
int count = 0;
for (int j = 0; j < n; j++) {
// Contribution of i-th
// greatest element to the cost
int p = a[j] - j;
// Remove the element
a[j] = 0;
// If negative
if (p < 0) {
p = 0;
continue;
}
// Add to the final cost
count += p;
}
// Return the cost
return count;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 6, 7, 4, 2, 5, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << findCost(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the total cost
// of removing all array elements
static int findCost(Integer [] a, int n)
{
// Sort the array in descending order
Arrays.sort(a, Collections.reverseOrder());
// Stores the total cost
int count = 0;
for (int j = 0; j < n; j++)
{
// Contribution of i-th
// greatest element to the cost
int p = a[j] - j;
// Remove the element
a[j] = 0;
// If negative
if (p < 0)
{
p = 0;
continue;
}
// Add to the final cost
count += p;
}
// Return the cost
return count;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
Integer arr[] = {1, 6, 7,
4, 2, 5, 3};
int N = arr.length;
// Function Call
System.out.print(findCost(arr, N));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach # Function to find the total cost # of removing all array elements def findCost(a, n): # Sort the array in descending order a.sort(reverse = True) # Stores the total cost count = 0 for j in range(n): # Contribution of i-th # greatest element to the cost p = a[j] - j # Remove the element a[j] = 0 # If negative if(p < 0): p = 0 continue # Add to the final cost count += p # Return the cost return count # Driver Code # Given array arr[] arr = [ 1, 6, 7, 4, 2, 5, 3 ] N = len(arr) # Function call print(findCost(arr, N)) # This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the total cost
// of removing all array elements
static int findCost(int []a, int n)
{
// Sort the array in descending order
Array.Sort(a);
Array.Reverse(a);
// Stores the total cost
int count = 0;
for (int j = 0; j < n; j++)
{
// Contribution of i-th
// greatest element to the cost
int p = a[j] - j;
// Remove the element
a[j] = 0;
// If negative
if (p < 0)
{
p = 0;
continue;
}
// Add to the readonly cost
count += p;
}
// Return the cost
return count;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = {1, 6, 7,
4, 2, 5, 3};
int N = arr.Length;
// Function Call
Console.Write(findCost(arr, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for the above approach
// Function to find the total cost
// of removing all array elements
function findCost(a, n) {
// Sort the array in descending order
a.sort((x, y) => y - x);
// Stores the total cost
var count = 0;
for (var j = 0; j < n; j++) {
// Contribution of i-th
// greatest element to the cost
var p = a[j] - j;
// Remove the element
a[j] = 0;
// If negative
if (p < 0) {
p = 0;
continue;
}
// Add to the final cost
count += p;
}
// Return the cost
return count;
}
// Driver Code
// Given array arr[]
var arr = [1, 6, 7, 4, 2, 5, 3];
var N = arr.length;
// Function Call
document.write(findCost(arr, N));
</script>
16
Complejidad de tiempo: O(NlogN), donde N es el tamaño de la array dada.
Espacio Auxiliar: O(1)