Dadas dos arrays A1 y A2 de N números. Hay dos personas, A y B, que seleccionan números de N. Si A selecciona el número i-ésimo, entonces se le pagará una cantidad de dinero A1[i] y si B selecciona el número i-ésimo, se le pagará A2[i]. ] cantidad de dinero pero A no puede seleccionar más de X números y B no puede seleccionar más de Y números. La tarea es seleccionar N números de tal manera que la cantidad de dinero total se maximice al final.
Nota: X + Y >= N
Examples:
Input: N = 5, X = 3, Y = 3
A1[] = {1, 2, 3, 4, 5},
A2= {5, 4, 3, 2, 1}
Output: 21
B will take the first 3 orders and A
will take the last two orders.
Input: N = 2, X = 1, Y = 1
A1[] = {10, 10}, A2= {20, 20}
Output: 30
Enfoque: Vamos a crear una nueva array C tal que C[i] = A2[i] – A1[i] . Ahora ordenaremos la array C en orden decreciente. Tenga en cuenta que la condición X + Y >= Ngarantiza que podremos asignar el número a cualquiera de las personas. Suponga que para algún i, A1[i] > A2[i] y usted asignó una orden a B, la pérdida encontrada debido a esta asignación es C[i]. De manera similar, para algún i, A2[i] > A1[i] y usted asignó un número a A, la pérdida encontrada debido a esta asignación es C[i]. Como queremos minimizar la pérdida encontrada, es mejor procesar los números que tienen pérdidas altas posibles, porque podemos intentar reducir la pérdida en la parte inicial. No tiene sentido seleccionar un número con una gran pérdida después de asignar un número con menos pérdida. Por lo tanto, inicialmente asignamos todos los números a A inicialmente, luego restamos la pérdida de ellos con avidez. Una vez que el número de pedido asignado está debajo de X, almacenamos el máximo de eso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to maximize profit
#include <bits/stdc++.h>
using namespace std;
// Function that maximizes the sum
int maximize(int A1[], int A2[], int n,
int x, int y)
{
// Array to store the loss
int c[n];
// Initial sum
int sum = 0;
// Generate the array C
for (int i = 0; i < n; i++) {
c[i] = A2[i] - A1[i];
sum += A1[i];
}
// Sort the array elements
// in descending order
sort(c, c + n, greater<int>());
// Variable to store the answer
int maxi = -1;
// Iterate in the array, C
for (int i = 0; i < n; i++) {
// Subtract the loss
sum += c[i];
// Check if X orders are going
// to be used
if (i + 1 >= (n - x))
maxi = max(sum, maxi);
}
return maxi;
}
// Driver Code
int main()
{
int A1[] = { 1, 2, 3, 4, 5 };
int A2[] = { 5, 4, 3, 2, 1 };
int n = 5;
int x = 3, y = 3;
cout << maximize(A1, A2, n, x, y);
return 0;
}
Java
// Java program to maximize profit
import java.util.*;
class GFG
{
// Function that maximizes the sum
static int maximize(int A1[], int A2[], int n,
int x, int y)
{
// Array to store the loss
int[] c = new int[n];
// Initial sum
int sum = 0;
// Generate the array C
for (int i = 0; i < n; i++)
{
c[i] = A2[i] - A1[i];
sum += A1[i];
}
// Sort the array elements
// in descending order
int temp;
for(int i = 0; i < n - 1; i++)
{
if(c[i] < c[i+1])
{
temp = c[i];
c[i] = c[i + 1];
c[i + 1] = temp;
}
}
// Variable to store the answer
int maxi = -1;
// Iterate in the array, C
for (int i = 0; i < n; i++)
{
// Subtract the loss
sum += c[i];
// Check if X orders are going
// to be used
if (i + 1 >= (n - x))
maxi = Math.max(sum, maxi);
}
return maxi;
}
// Driver Code
public static void main(String args[])
{
int A1[] = { 1, 2, 3, 4, 5 };
int A2[] = { 5, 4, 3, 2, 1 };
int n = 5;
int x = 3, y = 3;
System.out.println(maximize(A1, A2, n, x, y));
}
}
// This code is contributed by
// Surendra_Gangwar
Python3
# Python3 program to maximize profit # Function that maximizes the Sum def maximize(A1, A2, n, x, y): # Array to store the loss c = [0 for i in range(n)] # Initial Sum Sum = 0 # Generate the array C for i in range(n): c[i] = A2[i] - A1[i] Sum += A1[i] # Sort the array elements # in descending order c.sort() c = c[::-1] # Variable to store the answer maxi = -1 # Iterate in the array, C for i in range(n): # Subtract the loss Sum += c[i] # Check if X orders are going # to be used if (i + 1 >= (n - x)): maxi = max(Sum, maxi) return maxi # Driver Code A1 = [ 1, 2, 3, 4, 5 ] A2 = [ 5, 4, 3, 2, 1 ] n = 5 x, y = 3, 3 print(maximize(A1, A2, n, x, y)) # This code is contributed # by Mohit Kumar
C#
// C# program to maximize profit
using System;
class GFG
{
// Function that maximizes the sum
static int maximize(int [] A1, int [] A2, int n,
int x, int y)
{
// Array to store the loss
int [] c = new int[n];
// Initial sum
int sum = 0;
// Generate the array C
for (int i = 0; i < n; i++)
{
c[i] = A2[i] - A1[i];
sum += A1[i];
}
// Sort the array elements
// in descending order
int temp;
for(int i = 0; i < n - 1; i++)
{
if(c[i] < c[i+1])
{
temp = c[i];
c[i] = c[i + 1];
c[i + 1] = temp;
}
}
// Variable to store the answer
int maxi = -1;
// Iterate in the array, C
for (int i = 0; i < n; i++)
{
// Subtract the loss
sum += c[i];
// Check if X orders are going
// to be used
if (i + 1 >= (n - x))
maxi = Math.Max(sum, maxi);
}
return maxi;
}
// Driver Code
public static void Main()
{
int [] A1 = { 1, 2, 3, 4, 5 };
int [] A2 = { 5, 4, 3, 2, 1 };
int n = 5;
int x = 3, y = 3;
Console.WriteLine(maximize(A1, A2, n, x, y));
}
}
// This code is contributed by ihritik
PHP
<?php
// PHP program to maximize profit
// Function that maximizes the sum
function maximize($A1, $A2, $n, $x, $y)
{
# Array to store the loss
$c = array();
# Initial sum
$sum = 0;
// Generate the array C
for ($i = 0; $i < $n; $i++)
{
$c[$i] = $A2[$i] - $A1[$i];
$sum += $A1[$i];
}
// Sort the array elements
// in descending order
rsort($c);
// Variable to store the answer
$maxi = -1;
// Iterate in the array, C
for ($i = 0; $i < $n; $i++)
{
// Subtract the loss
$sum += $c[$i];
// Check if X orders are going
// to be used
if ($i + 1 >= ($n - $x))
$maxi = max($sum, $maxi);
}
return $maxi;
}
# Driver Code
$A1 = array( 1, 2, 3, 4, 5 );
$A2 = array( 5, 4, 3, 2, 1 );
$n = 5;
$x = 3;
$y = 3;
echo maximize($A1, $A2, $n, $x, $y);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function that maximizes the sum
function maximize(A1, A2, n,
x, y)
{
// Array to store the loss
let c = Array(n).fill(0);
// Initial sum
let sum = 0;
// Generate the array C
for (let i = 0; i < n; i++)
{
c[i] = A2[i] - A1[i];
sum += A1[i];
}
// Sort the array elements
// in descending order
let temp;
for(let i = 0; i < n - 1; i++)
{
if(c[i] < c[i+1])
{
temp = c[i];
c[i] = c[i + 1];
c[i + 1] = temp;
}
}
// Variable to store the answer
let maxi = -1;
// Iterate in the array, C
for (let i = 0; i < n; i++)
{
// Subtract the loss
sum += c[i];
// Check if X orders are going
// to be used
if (i + 1 >= (n - x))
maxi = Math.max(sum, maxi);
}
return maxi;
}
// Driver code
let A1 = [ 1, 2, 3, 4, 5 ];
let A2 = [ 5, 4, 3, 2, 1 ];
let n = 5;
let x = 3, y = 3;
document.write(maximize(A1, A2, n, x, y));
</script>
21
Complejidad de tiempo: O(N*logN), ya que estamos usando una función de clasificación incorporada que cuesta N*logN de tiempo.
Espacio Auxiliar: O(N), ya que estamos usando espacio extra del arreglo c. Donde N es el número de elementos en los arreglos.