Potencia máxima en N niveles desde K, de modo que derrotar al jefe en el nivel A[i] aumenta la potencia en B[i]

Dadas dos arrays a[] y b[] de tamaño N y un entero K . La tarea es encontrar el poder máximo que se puede lograr en N niveles con poder inicial K tal que después de derrotar al jefe de nivel i-ésimo de fuerza a[i] , el poder se incrementa en b[i] . Para derrotar a un jefe, el poder debe ser mayor o igual a su poder.

Ejemplos:

Entrada: N = 3, K = 10, a[] = {20, 30, 10}, b[] = {9, 100, 10}  
Salida: 29
Explicación: Primero derrota al jefe en el índice 3, el poder se convierte en 20, luego derrota al jefe en el índice 1 y el poder se convierte en 29. Ahora no puedes derrotar a ningún otro jefe, por lo que 29 es el poder máximo que puedes alcanzar.
 

Entrada: N = 2, K = 5, a[] = {7, 10}, b[] = {100, 20}  
Salida: 5

Enfoque: la tarea se puede resolver utilizando el enfoque codicioso . Encuentra al jefe más débil y comprueba si tu poder es mayor o igual que su poder. En caso afirmativo, derrota al jefe y toma la caja mágica i que aumentará tu poder en b[i] . Sigue repitiendo este paso hasta que no quede ninguna caja mágica para tomar o no puedas derrotar al jefe más débil. Siga los pasos a continuación para resolver el problema:

• Encontrar al jefe más débil se puede hacer fácilmente usando una cola de prioridad mínima . Tenga en cuenta que almacenaremos los valores en la cola de prioridad en pares, es decir, {a[i], b[i]} para que el jefe más débil esté siempre en la parte superior de la cola de prioridad. 

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum power you can achieve.
int maxPower(int a[], int b[], int n, int k)
{
    priority_queue<pair<int, int>, vector<pair<int, int> >,
                   greater<pair<int, int> > >
        pq;
    for (int i = 0; i < n; i++)
        pq.push({ a[i], b[i] });
 
    int cur_power = k;
 
    while (!pq.empty()) {
        int guard_power = pq.top().first;
        int extra_power = pq.top().second;
        pq.pop();
 
        // The weakest guard has more power than you.
        if (guard_power > cur_power)
            break;
 
        // Defeat the current guard
        // and add extra power
        // to your current power.
        cur_power += extra_power;
    }
 
    return cur_power;
}
 
// Driver function
int main()
{
    int a[] = { 20, 30, 10 };
    int b[] = { 9, 100, 10 };
    int n = sizeof(a) / sizeof(a[0]);
    int k = 10;
 
    // Function Call
    cout << maxPower(a, b, n, k);
    return 0;
}

# python program for the above approach
from queue import PriorityQueue
 
# Function to find the maximum power you can achieve.
def maxPower(a, b, n, k):
 
    pq = PriorityQueue()
 
    for i in range(0, n):
        pq.put([a[i], b[i]])
 
    cur_power = k
 
    while (not pq.empty()):
        pw = pq.get()
        guard_power = pw[0]
        extra_power = pw[1]
 
        # The weakest guard has more power than you.
        if (guard_power > cur_power):
            break
 
            # Defeat the current guard
            # and add extra power
            # to your current power.
        cur_power += extra_power
 
    return cur_power
 
# Driver function
if __name__ == "__main__":
 
    a = [20, 30, 10]
    b = [9, 100, 10]
    n = len(a)
    k = 10
 
    # Function Call
    print(maxPower(a, b, n, k))
 
    # This code is contributed by rakeshsahni

29

Complejidad de tiempo : O(N log(N))
Espacio auxiliar : O(N)