Dada una array arr[] que consiste en N enteros positivos tales que arr[i] representa que la i -ésima bolsa contiene arr[i] diamantes y un entero positivo K , la tarea es encontrar el número máximo de diamantes que se pueden ganar en exactamente K minutos si dejar caer una bolsa toma 1 minuto, de modo que si se deja caer una bolsa con P diamantes, entonces cambia a [P/2] diamantes y se ganan P diamantes.
Ejemplos:
Entrada: arr[] = {2, 1, 7, 4, 2}, K = 3
Salida: 14
Explicación:
El estado inicial de las bolsas es {2, 1, 7, 4, 2}.
Operación 1: Tome todos los diamantes de la tercera bolsa, es decir, arr[2](= 7), el estado de las bolsas se convierte en: {2, 1, 3, 4, 2}.
Operación 2: Tome todos los diamantes de la cuarta bolsa, es decir, arr[3](= 4), el estado de las bolsas se convierte en: {2, 1, 3, 2, 2}.
Operación 3: Tome todos los diamantes de la tercera bolsa, es decir, arr[2](= 3), el estado de las bolsas se convierte en {2, 1, 1, 2, 2}.
Por lo tanto, la ganancia total de diamantes es 7 + 4 + 3 = 14.Entrada: arr[] = {7, 1, 2}, K = 2
Salida: 10
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso con la ayuda de max-heap . Siga los pasos a continuación para resolver el problema:
- Inicialice una cola de prioridad , digamos PQ , e inserte todos los elementos de la array dada en PQ .
- Inicialice una variable, digamos ans como 0 para almacenar el diamante máximo obtenido resultante.
- Iterar un bucle hasta que la cola de prioridad PQ no esté vacía y el valor de K > 0 :
- Extraiga el elemento superior de la cola de prioridad y agregue el elemento emergente a la variable ans .
- Divida el elemento reventado por 2 e insértelo en la cola de prioridad PQ .
- Disminuya el valor de K en 1 .
- Después de completar los pasos anteriores, imprima el valor de ans 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 number
// of diamonds that can be gained in
// exactly K minutes
void maxDiamonds(int A[], int N, int K)
{
// Stores all the array elements
priority_queue<int> pq;
// Push all the elements to the
// priority queue
for (int i = 0; i < N; i++) {
pq.push(A[i]);
}
// Stores the required result
int ans = 0;
// Loop while the queue is not
// empty and K is positive
while (!pq.empty() && K--) {
// Store the top element
// from the pq
int top = pq.top();
// Pop it from the pq
pq.pop();
// Add it to the answer
ans += top;
// Divide it by 2 and push it
// back to the pq
top = top / 2;
pq.push(top);
}
// Print the answer
cout << ans;
}
// Driver Code
int main()
{
int A[] = { 2, 1, 7, 4, 2 };
int K = 3;
int N = sizeof(A) / sizeof(A[0]);
maxDiamonds(A, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the maximum number
// of diamonds that can be gained in
// exactly K minutes
static void maxDiamonds(int A[], int N, int K)
{
// Stores all the array elements
PriorityQueue<Integer> pq = new PriorityQueue<>(
(a, b) -> b - a);
// Push all the elements to the
// priority queue
for(int i = 0; i < N; i++)
{
pq.add(A[i]);
}
// Stores the required result
int ans = 0;
// Loop while the queue is not
// empty and K is positive
while (!pq.isEmpty() && K-- > 0)
{
// Store the top element
// from the pq
int top = pq.peek();
// Pop it from the pq
pq.remove();
// Add it to the answer
ans += top;
// Divide it by 2 and push it
// back to the pq
top = top / 2;
pq.add(top);
}
// Print the answer
System.out.print(ans);
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 2, 1, 7, 4, 2 };
int K = 3;
int N = A.length;
maxDiamonds(A, N, K);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to find the maximum number # of diamonds that can be gained in # exactly K minutes def maxDiamonds(A, N, K): # Stores all the array elements pq = [] # Push all the elements to the # priority queue for i in range(N): pq.append(A[i]) pq.sort() # Stores the required result ans = 0 # Loop while the queue is not # empty and K is positive while (len(pq) > 0 and K > 0): pq.sort() # Store the top element # from the pq top = pq[len(pq) - 1] # Pop it from the pq pq = pq[0:len(pq) - 1] # Add it to the answer ans += top # Divide it by 2 and push it # back to the pq top = top // 2; pq.append(top) K -= 1 # Print the answer print(ans) # Driver Code if __name__ == '__main__': A = [ 2, 1, 7, 4, 2 ] K = 3 N = len(A) maxDiamonds(A, N, K) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to find the maximum number
// of diamonds that can be gained in
// exactly K minutes
static void maxDiamonds(int []A, int N, int K)
{
// Stores all the array elements
var pq = new List<int>();
// Push all the elements to the
// priority queue
for(int i = 0; i < N; i++)
{
pq.Add(A[i]);
}
// Stores the required result
int ans = 0;
// Loop while the queue is not
// empty and K is positive
while (pq.Count!=0 && K-- > 0)
{
pq.Sort();
// Store the top element
// from the pq
int top = pq[pq.Count-1];
// Pop it from the pq
pq.RemoveAt(pq.Count-1);
// Add it to the answer
ans += top;
// Divide it by 2 and push it
// back to the pq
top = top / 2;
pq.Add(top);
}
// Print the answer
Console.WriteLine(ans);
}
// Driver Code
public static void Main(string[] args)
{
int []A= { 2, 1, 7, 4, 2 };
int K = 3;
int N = A.Length;
maxDiamonds(A, N, K);
}
}
// This code is contributed by rrrtnx.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the maximum number
// of diamonds that can be gained in
// exactly K minutes
function maxDiamonds(A, N, K) {
// Stores all the array elements
let pq = [];
// Push all the elements to the
// priority queue
for (let i = 0; i < N; i++) {
pq.push(A[i]);
}
// Stores the required result
let ans = 0;
// Loop while the queue is not
// empty and K is positive
pq.sort((a, b) => a - b)
while (pq.length && K--) {
pq.sort((a, b) => a - b)
// Store the top element
// from the pq
let top = pq[pq.length - 1];
// Pop it from the pq
pq.pop();
// Add it to the answer
ans += top;
// Divide it by 2 and push it
// back to the pq
top = Math.floor(top / 2);
pq.push(top);
}
// Print the answer
document.write(ans);
}
// Driver Code
let A = [2, 1, 7, 4, 2];
let K = 3;
let N = A.length;
maxDiamonds(A, N, K);
</script>
14
Complejidad de tiempo: O((N + K)*log N)
Espacio auxiliar: O(N)