Calculadora de propinas máximas | conjunto 2

Rahul y Ankit son los dos únicos camareros del Royal Restaurant. Hoy, el restaurante recibió N pedidos. La cantidad de propinas puede diferir cuando las manejan diferentes camareros y se dan como arrays A[] y B[] , de modo que si Rahul toma la i ^-ésima orden, recibirá una propina de A[i] rupias, y si Ankit toma esta orden, el La propina sería B[i] rupias. Para maximizar el valor total de la propina, decidieron distribuir el pedido entre ellos. Un pedido será manejado por una sola persona . Además, debido a limitaciones de tiempo, Rahul no puede tomar más de Xpedidos y Ankit no puede aceptar más de Y pedidos. Se garantiza que X + Y es mayor o igual que N , lo que significa que todos los pedidos pueden ser manejados por Rahul o Ankit. La tarea es averiguar la cantidad máxima posible de dinero total de propinas después de procesar todos los pedidos.

Ejemplos:

Entrada: N = 5, X = 3, Y = 3, A[] = {1, 2, 3, 4, 5}, B[] = {5, 4, 3, 2, 1}
Salida: 21
Explicación:
Paso 1: 5 está incluido en la array de Ankit 
Paso 2: 4 está incluido en la array de Ankit 
Paso 3: Como ambos tienen el mismo valor 3, elija cualquiera de ellos 
Paso 4: 4 está incluido en la array de Rahul 
Paso 5: 5 está incluido de la array de Rahul 
Por lo tanto, la cantidad máxima posible de dinero total de propinas suma 21.

Entrada: N = 7, X = 3, Y = 4, A[] = {8, 7, 15, 19, 16, 16, 18}, B[] = {1, 7, 15, 11, 12, 31 , 9} 
Salida: 110

Enfoque ingenuo: El enfoque ingenuo para resolver este artículo se analiza en el artículo anterior.

Enfoque eficiente: la idea es utilizar la técnica codiciosa para resolver el problema. Ordena los N pedidos en orden decreciente según la diferencia entre la propina de Rahul y la propina de Ankit. Luego, recorra todas las órdenes y tome la punta máxima de la i ^-ésima orden si es posible. Siga los pasos a continuación para resolver el problema:

• Inicialice ans como 0 para almacenar la máxima propina posible.
• Cree un vector de par de enteros, V de tamaño N tal que el primer y segundo elemento de V[i] almacene la punta del i ^-ésimo orden de Rahul y Ankit respectivamente.
• Ordene el vector , V en orden decreciente sobre la base de la diferencia entre las puntas.
• Recorrer el vector , V usando la variable i
  • Si el valor de Y es 0 O la condición V[i].primero ≥ V[i].segundo se cumple, entonces sume el valor de V[i].primero a ans y disminuya X en 1 .
  • De lo contrario, agregue el valor de V[i].segundo a ans y disminuya Y 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++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Utility Compare function
// for sorting the array
bool compare(pair<int, int> p1, pair<int, int> p2)
{
    return abs(p1.first - p1.second)
           > abs(p2.first - p2.second);
}
 
// Function to find the maximum possible amount of total
// tip money after processing all the orders
void maxTip(int A[], int B[], int X, int Y, int N)
{
    // Store all the N orders
    vector<pair<int, int> > tips(N);
 
    // Traverse all the orders and add them
    // to the vector, V
    for (int i = 0; i < N; i++) {
        tips[i].first = A[i];
        tips[i].second = B[i];
    }
 
    // Sort the vector in decreasing
      // order of absolute
    // difference of the tips value
    sort(tips.begin(), tips.end(), compare);
 
    // Store the required result
    int ans = 0;
 
    // Traverse all the orders
    for (int i = 0; i < N; i++) {
 
        // Check if Y is 0 or Rahul's tip value
        // is greater than or equal to that of Ankit
        if (Y == 0
            || (X > 0 && tips[i].first >= tips[i].second)) {
 
            // Update the overall result and
            // decrement X by 1
            ans += tips[i].first;
            X--;
        }
 
        else {
 
            // Update the overall result and
            // decrement Y by 1
            ans += tips[i].second;
            Y--;
        }
    }
 
    // Print the result
    cout << ans;
}
 
// Driver Code
int main()
{
    // Given input
    int N = 5, X = 3, Y = 3;
    int A[] = { 1, 2, 3, 4, 5 };
    int B[] = { 5, 4, 3, 2, 1 };
 
    // Function Call
    maxTip(A, B, X, Y, N);
 
    return 0;
}

<script>
 
// JavaScript program for the above approach
 
 
// Utility Compare function
// for sorting the array
function compare(p1, p2)
{
    return Math.abs(p2[0] - p2[1]) - Math.abs(p1[0] - p1[1]);
}
 
// Function to find the maximum possible amount of total
// tip money after processing all the orders
function maxTip(A, B, X, Y, N)
{
    // Store all the N orders
    let tips = new Array(N);
 
    // Traverse all the orders and add them
    // to the vector, V
    for (let i = 0; i < N; i++) {
        tips[i] = new Array();
        tips[i][0] = A[i];
        tips[i][1] = B[i];
    }
 
    // Sort the vector in decreasing
    // order of absolute
    // difference of the tips value
    tips.sort(compare);
 
    // Store the required result
    let ans = 0;
 
    // Traverse all the orders
    for (let i = 0; i < N; i++) {
 
        // Check if Y is 0 or Rahul's tip value
        // is greater than or equal to that of Ankit
        if (Y == 0
            || (X > 0 && tips[i][0] >= tips[i][1])) {
 
            // Update the overall result and
            // decrement X by 1
            ans += tips[i][0];
            X--;
        }
 
        else {
 
            // Update the overall result and
            // decrement Y by 1
            ans += tips[i][1];
            Y--;
        }
    }
 
    // Print the result
    document.write(ans,"</br>");
}
 
// Driver Code
 
// Given input
let N = 7, X = 3, Y = 4;
let A = [8, 7, 15, 19, 16, 16, 18];
let B = [1, 7, 15, 11, 12, 31, 9];
 
 
// Function Call
maxTip(A, B, X, Y, N);
 
// This code is contributed by shinjanpatra.
</script>

21

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