Maximice la suma de elementos X+Y eligiendo elementos X e Y del primer y segundo arreglo

Dadas dos arrays de tamaño N y dos números X e Y, la tarea es maximizar la suma considerando los siguientes puntos:

• Elija valores x de la primera array y valores y de la segunda array de modo que la suma de los valores X+Y sea máxima.
• Se da que X + Y es igual a N.

Ejemplos:  

Entrada: arr1[] = {1, 4, 1}, arr2[] = {2, 5, 3}, N = 3, X = 2, Y = 1 
Salida: 8 
Para maximizar la suma de 2 arrays, 
seleccione 1er y 2do elemento del primer arreglo y 3ro del segundo arreglo.

Entrada: A[] = {1, 4, 1, 2}, B[] = {4, 3, 2, 5}, N = 4, X = 2, Y = 2 
Salida: 14

Enfoque: se puede utilizar un enfoque codicioso para resolver el problema anterior. A continuación se detallan los pasos necesarios:  

• Encuentre primero los elementos de las arrays que tienen el valor máximo al encontrar la diferencia más alta entre los elementos de dos arrays.
• Para eso, encuentre la diferencia absoluta entre el valor de la primera y la segunda array y luego guárdela en otra array.
• Ordena esta array en orden decreciente.
• Mientras ordena, rastree las posiciones originales de los elementos en las arrays.
• Ahora compare los elementos de las dos arrays y agregue el valor mayor a maxAmount.
• Si ambos tienen el mismo valor, agregue un elemento de la primera array, si X no es cero, de lo contrario, agregue un elemento de la segunda array.
• Después de recorrer las arrays por completo, devuelva el maxAmount calculado.

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

// C++ program to print the maximum
// possible sum from two arrays.
#include <bits/stdc++.h>
using namespace std;
 
// class that store values of two arrays
// and also store their absolute difference
class triplet {
public:
    int first;
    int second;
    int diff;
    triplet(int f, int s, int d)
        : first(f), second(s), diff(d)
    {
    }
};
 
// Compare function used to sort array in decreasing order
bool compare(triplet& a, triplet& b)
{
    return a.diff > b.diff; // decreasing order
}
 
/// Function to find the maximum possible
/// sum that can be generated from 2 arrays
int findMaxAmount(int arr1[], int arr2[], int n, int x, int y)
{
    // vector where each index stores 3 things:
    // Value of 1st array
    // Value of 2nd array
    // Their absolute difference
    vector<triplet> v;
 
    for (int i = 0; i < n; i++) {
        triplet t(arr1[i], arr2[i], abs(arr1[i] - arr2[i]));
        v.push_back(t);
    }
 
    // sort according to their absolute difference
    sort(v.begin(), v.end(), compare);
 
    // it will store maximum sum
    int maxAmount = 0;
 
    int i = 0;
 
    // Run loop for N times or
    // value of X or Y becomes zero
    while (i < n && x > 0 && y > 0) {
 
        // if 1st array element has greater
        // value, add it to maxAmount
        if (v[i].first > v[i].second) {
            maxAmount += v[i].first;
            x--;
        }
 
        // if 2nd array element has greater
        // value, add it to maxAmount
        if (v[i].first < v[i].second) {
            maxAmount += v[i].second;
            y--;
        }
 
        // if both have same value, add element
        // of first array if X is not zero
        // else add element of second array
        if (v[i].first == v[i].second) {
            if (x > 0) {
                maxAmount += v[i].first;
                x--;
            }
            else if (y > 0) {
                maxAmount += v[i].second;
                y--;
            }
        }
 
        // increment after picking element
        i++;
    }
 
    // add the remaining values
    // of first array to maxAmount
    while (i < v.size() && x--) {
        maxAmount += v[i++].first;
    }
 
    // add the remaining values of
    // second array to maxAmount
    while (i < v.size() && y--) {
        maxAmount += v[i++].second;
    }
 
    return maxAmount;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 4, 1, 2 };
    int B[] = { 4, 3, 2, 5 };
    int n = sizeof(A) / sizeof(A[0]);
 
    int X = 2, Y = 2;
 
    cout << findMaxAmount(A, B, n, X, Y) << "\n";
}

// Java program to print the maximum
// possible sum from two arrays.
import java.util.*;
 
// class that store values of two arrays
// and also store their absolute difference
class Triplet implements Comparable<Triplet>
{
    int first;
    int second;
    int diff;
 
    Triplet(int f, int s, int d)
    {
        first = f;
        second = s;
        diff = d;
    }
     
    // CompareTo function used to sort
    // array in decreasing order
    public int compareTo(Triplet o)
    {
        return o.diff - this.diff;
    }
}
class GFG{
 
// Function to find the maximum possible
// sum that can be generated from 2 arrays
public static int findMaxAmount(int arr1[],
                                int arr2[],
                                int n, int x,
                                int y)
{
     
    // Vector where each index
    // stores 3 things:
    // Value of 1st array
    // Value of 2nd array
    // Their absolute difference
    Vector<Triplet> v = new Vector<>();
 
    for(int i = 0; i < n; i++)
    {
       v.add(new Triplet(arr1[i], arr2[i],
                         Math.abs(arr1[i] -
                                  arr2[i])));
    }
 
    // Sort according to their
    // absolute difference
    Collections.sort(v);
 
    // It will store maximum sum
    int maxAmount = 0;
 
    int i = 0;
 
    // Run loop for N times or
    // value of X or Y becomes zero
    while (i < n && x > 0 && y > 0)
    {
         
        // If 1st array element has greater
        // value, add it to maxAmount
        if (v.get(i).first > v.get(i).second)
        {
            maxAmount += v.get(i).first;
            x--;
        }
 
        // If 2nd array element has greater
        // value, add it to maxAmount
        if (v.get(i).first < v.get(i).second)
        {
            maxAmount += v.get(i).second;
            y--;
        }
     
        // If both have same value, add element
        // of first array if X is not zero
        // else add element of second array
        if (v.get(i).first == v.get(i).second)
        {
            if (x > 0)
            {
                maxAmount += v.get(i).first;
                x--;
            }
            else if (y > 0)
            {
                maxAmount += v.get(i).second;
                y--;
            }
        }
         
        // Increment after picking element
        i++;
    }
 
    // Add the remaining values
    // of first array to maxAmount
    while (i < v.size() && x-- > 0)
    {
        maxAmount += v.get(i++).first;
    }
 
    // Add the remaining values of
    // second array to maxAmount
    while (i < v.size() && y-- > 0)
    {
        maxAmount += v.get(i++).second;
    }
     
    return maxAmount;
}
 
// Driver Code
public static void main(String []args)
{
    int A[] = { 1, 4, 1, 2 };
    int B[] = { 4, 3, 2, 5 };
    int n = A.length;
 
    int X = 2, Y = 2;
 
    System.out.println(findMaxAmount(A, B, n, X, Y));
}
}
 
// This code is contributed by jrishabh99

# Python3 program to print the maximum
# possible sum from two arrays.
 
# Class that store values of two arrays
# and also store their absolute difference
class triplet:
     
    def __init__(self, f, s, d):
        self.first = f
        self.second = s
        self.diff = d
 
# Function to find the maximum possible
# sum that can be generated from 2 arrays
def findMaxAmount(arr1, arr2, n, x, y):
 
    # vector where each index stores 3 things:
    # Value of 1st array
    # Value of 2nd array
    # Their absolute difference
    v = []
 
    for i in range(0, n):
        t = triplet(arr1[i], arr2[i],
                abs(arr1[i] - arr2[i]))
        v.append(t)
 
    # sort according to their absolute difference
    v.sort(key = lambda x: x.diff, reverse = True)
 
    # it will store maximum sum
    maxAmount, i = 0, 0
 
    # Run loop for N times or
    # value of X or Y becomes zero
    while i < n and x > 0 and y > 0:
 
        # if 1st array element has greater
        # value, add it to maxAmount
        if v[i].first > v[i].second:
            maxAmount += v[i].first
            x -= 1
 
        # if 2nd array element has greater
        # value, add it to maxAmount
        if v[i].first < v[i].second:
            maxAmount += v[i].second
            y -= 1
 
        # if both have same value, add element
        # of first array if X is not zero
        # else add element of second array
        if v[i].first == v[i].second:
            if x > 0:
                maxAmount += v[i].first
                x -= 1
             
            elif y > 0:
                maxAmount += v[i].second
                y -= 1
 
        # increment after picking element
        i += 1
     
    # add the remaining values
    # of first array to maxAmount
    while i < len(v) and x > 0:
        maxAmount += v[i].first
        i, x = i + 1, x - 1
 
    # add the remaining values of
    # second array to maxAmount
    while i < len(v) and y > 0:
        maxAmount += v[i].second
        i, y = i + 1, y - 1
     
    return maxAmount
 
# Driver Code
if __name__ == "__main__":
 
    A = [1, 4, 1, 2]
    B = [4, 3, 2, 5]
    n = len(A)
 
    X, Y = 2, 2
 
    print(findMaxAmount(A, B, n, X, Y))
 
# This code is contributed by Rituraj Jain

<script>
 
// JavaScript program to print the maximum
// possible sum from two arrays.
 
// Class that store values of two arrays
// && also store their absolute difference
class triplet{
     
    constructor(f, s, d){
        this.first = f
        this.second = s
        this.diff = d
    }
}
// Function to find the maximum possible
// sum that can be generated from 2 arrays
function findMaxAmount(arr1, arr2, n, x, y){
 
    // vector where each index stores 3 things:
    // Value of 1st array
    // Value of 2nd array
    // Their absolute difference
    let v = []
 
    for(let i = 0; i < n; i++){
        let t = new triplet(arr1[i], arr2[i],
                Math.abs(arr1[i] - arr2[i]))
        v.push(t)
    }
 
    // sort according to their absolute difference
    v.sort((a,b) => b.diff - a.diff)
 
    // it will store maximum sum
    let maxAmount=0, i = 0
 
    // Run loop for N times or
    // value of X or Y becomes zero
    while(i < n && x > 0 && y > 0){
 
        // if 1st array element has greater
        // value, add it to maxAmount
        if(v[i].first > v[i].second){
            maxAmount += v[i].first
            x -= 1
        }
 
        // if 2nd array element has greater
        // value, add it to maxAmount
        if(v[i].first < v[i].second){
            maxAmount += v[i].second
            y -= 1
        }
        // if both have same value, add element
        // of first array if X is not zero
        // else add element of second array
        if(v[i].first == v[i].second){
            if(x > 0){
                maxAmount += v[i].first
                x--
            }
            else if (y > 0){
                maxAmount += v[i].second
                y--
            }
        }
 
        // increment after picking element
        i++
    }
     
    // add the remaining values
    // of first array to maxAmount
    while(i < v.length && x > 0){
        maxAmount += v[i].first
        i++
        x--
    }
    // add the remaining values of
    // second array to maxAmount
    while(i < v.length && y > 0){
        maxAmount += v[i].second
        i++
        y--
    }
     
    return maxAmount
}
 
// Driver Code
 
let A = [1, 4, 1, 2]
let B = [4, 3, 2, 5]
let n = A.length
 
let X = 2, Y = 2
 
document.write(findMaxAmount(A, B, n, X, Y))
 
// This code is contributed by shinjanpatra
 
</script>

14

Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)