Dada una array arr[] que consiste en N enteros positivos, tal que arr[i] representa el número de productos que tiene el i -ésimo proveedor y un entero positivo, M , la tarea es encontrar la ganancia máxima vendiendo M productos si la ganancia de un producto en particular es igual al número de productos restantes de ese proveedor.
Ejemplos:
Entrada: arr[] = {4, 6}, M = 4
Salida: 19
Explicación:
A continuación se muestra el orden de venta del producto para obtener el máximo beneficio:
Producto 1: Vender un producto del segundo proveedor, luego la array se modifica a {4, 5} y la ganancia es 6.
Producto 2: vende un producto del segundo proveedor, luego la array se modifica a {4, 4} y la ganancia es 6 + 5 = 11.
Producto 3: vende un producto del segundo proveedor. segundo proveedor, luego la array se modifica a {4, 3} y la ganancia es 6 + 5 + 4 = 15.
Producto 4: Vender un producto del primer proveedor, luego la array se modifica a {3, 3} y la ganancia es 6 + 5 + 4 + 4 = 19.
Por tanto, la máxima ganancia que se puede obtener vendiendo 4 productos es 19.Entrada: arr[] = {1, 2, 3}, M = 2
Salida: 5
Enfoque ingenuo: el problema dado se puede resolver vendiendo el producto a los proveedores que tienen la cantidad máxima actual de productos restantes. Entonces, la idea es iterar un ciclo M veces , y en cada iteración encontrar el valor del elemento más grande en la array , y agregar su valor a la ganancia y luego disminuir su valor en la array en 1. Después del ciclo, imprima el valor de la ganancia.
Complejidad de Tiempo: O(M * N)
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de Max-Heap para realizar un seguimiento del elemento máximo en la array en tiempo O (log N) . Siga los pasos a continuación para resolver el problema:
- Inicialice un Max-Heap usando una cola de prioridad , diga Q para realizar un seguimiento del elemento máximo presente en la array.
- Recorra la array arr[] e inserte todos los elementos en el montón Q.
- Inicialice una variable, digamos maxProfit como 0 para almacenar el resultado de la ganancia máxima obtenida.
- Iterar un bucle hasta M > 0 y realizar los siguientes pasos:
- Disminuya el valor de M en 1 .
- Almacene el valor del elemento superior de la cola de prioridad Q en una variable X y sáquelo de la cola de prioridad .
- Agregue el valor de X a la variable maxProfit e inserte (X – 1) a la variable Q.
- Después de completar los pasos anteriores, imprima el valor de maxProfit como resultado.
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 maximum profit
// by selling M number of products
void findMaximumProfit(int arr[], int M, int N)
{
// Initialize a Max-Heap to keep
// track of the maximum value
priority_queue<int> max_heap;
// Stores the maximum profit
int maxProfit = 0;
// Traverse the array and push
// all the elements in max_heap
for(int i = 0; i < N; i++)
max_heap.push(arr[i]);
// Iterate a loop until M > 0
while (M > 0)
{
// Decrement the value
// of M by 1
M--;
// Pop the maximum element
// from the heap
int X = max_heap.top();
max_heap.pop();
// Update the maxProfit
maxProfit += X;
// Push (X - 1) to max heap
max_heap.push(X - 1);
}
// Print the result
cout<<maxProfit;
}
// Driver Code
int main()
{
int arr[] = { 4, 6 };
int M = 4;
int N = sizeof(arr) / sizeof(arr[0]);
findMaximumProfit(arr, M, N);
}
// This code is contributed by bgangwar59
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the maximum profit
// by selling M number of products
static void findMaximumProfit(
int[] arr, int M, int N)
{
// Initialize a Max-Heap to keep
// track of the maximum value
PriorityQueue<Integer> max_heap
= new PriorityQueue<>((a, b) -> b - a);
// Stores the maximum profit
int maxProfit = 0;
// Traverse the array and push
// all the elements in max_heap
for (int i = 0; i < N; i++)
max_heap.add(arr[i]);
// Iterate a loop until M > 0
while (M > 0) {
// Decrement the value
// of M by 1
M--;
// Pop the maximum element
// from the heap
int X = max_heap.poll();
// Update the maxProfit
maxProfit += X;
// Push (X - 1) to max heap
max_heap.add(X - 1);
}
// Print the result
System.out.println(maxProfit);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 4, 6 };
int M = 4;
int N = arr.length;
findMaximumProfit(arr, M, N);
}
}
Python3
# Python3 program for the above approach # Function to find the maximum profit # by selling M number of products def findMaximumProfit(arr, M, N): # Initialize a Max-Heap to keep # track of the maximum value max_heap = [] # Stores the maximum profit maxProfit = 0 # Traverse the array and push # all the elements in max_heap for i in range(0, N): max_heap.append(arr[i]) max_heap.sort() max_heap.reverse() # Iterate a loop until M > 0 while (M > 0): # Decrement the value # of M by 1 M -= 1 # Pop the maximum element # from the heap X = max_heap[0] max_heap.pop(0) # Update the maxProfit maxProfit += X # Push (X - 1) to max heap max_heap.append(X - 1) max_heap.sort() max_heap.reverse() # Print the result print(maxProfit) # Driver code arr = [ 4, 6 ] M = 4 N = len(arr) findMaximumProfit(arr, M, N) # This code is contributed by rameshtravel07
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the maximum profit
// by selling M number of products
static void findMaximumProfit(int[] arr, int M, int N)
{
// Initialize a Max-Heap to keep
// track of the maximum value
List<int> max_heap = new List<int>();
// Stores the maximum profit
int maxProfit = 0;
// Traverse the array and push
// all the elements in max_heap
for(int i = 0; i < N; i++)
max_heap.Add(arr[i]);
max_heap.Sort();
max_heap.Reverse();
// Iterate a loop until M > 0
while (M > 0)
{
// Decrement the value
// of M by 1
M--;
// Pop the maximum element
// from the heap
int X = max_heap[0];
max_heap.RemoveAt(0);
// Update the maxProfit
maxProfit += X;
// Push (X - 1) to max heap
max_heap.Add(X - 1);
max_heap.Sort();
max_heap.Reverse();
}
// Print the result
Console.Write(maxProfit);
}
static void Main() {
int[] arr = { 4, 6 };
int M = 4;
int N = arr.Length;
findMaximumProfit(arr, M, N);
}
}
// This code is contributed by mukesh07.
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum profit
// by selling M number of products
function findMaximumProfit(arr, M, N)
{
// Initialize a Max-Heap to keep
// track of the maximum value
let max_heap = [];
// Stores the maximum profit
let maxProfit = 0;
// Traverse the array and push
// all the elements in max_heap
for(let i = 0; i < N; i++)
max_heap.push(arr[i]);
max_heap.sort(function(a, b){return a - b});
max_heap.reverse();
// Iterate a loop until M > 0
while (M > 0)
{
// Decrement the value
// of M by 1
M--;
// Pop the maximum element
// from the heap
let X = max_heap[0];
max_heap.shift();
// Update the maxProfit
maxProfit += X;
// Push (X - 1) to max heap
max_heap.push(X - 1);
max_heap.sort(function(a, b){return a - b});
max_heap.reverse();
}
// Print the result
document.write(maxProfit);
}
let arr = [ 4, 6 ];
let M = 4;
let N = arr.length;
findMaximumProfit(arr, M, N);
// This code is contributed by divyeshrabadiya07.
</script>
19
Complejidad de tiempo: O(M * log(N))
Espacio auxiliar: O(N)