Suma máxima seleccionando elementos de dos arrays en orden

Dadas dos arrays de tamaño N y dos enteros X e Y que indican el número máximo de elementos, uno puede elegir entre la array A y la array B respectivamente. 
En cada i ^-ésimo turno, se puede elegir A[i] o B[i] . La tarea es hacer la selección que resulte en la suma máxima posible. 
Nota: Se garantiza que (X + Y) ≥ N . 
Ejemplos: 
 

Entrada: A[] = {1, 2, 3, 4, 5}, B[] = {5, 4, 3, 2, 1}, X = 3, Y = 2 
Salida: 21 
i = 0 -> 5 elegido 
i = 1 -> 4 elegido 
i = 2 -> 3 elegido 
i = 3 -> 4 elegido 
i = 4 -> 5 elegido 
5 + 4 + 3 + 4 + 5 = 21
Entrada: A[] = {1, 4 , 3, 2, 7, 5, 9, 6}, B[] = {1, 2, 3, 6, 5, 4, 9, 8}, X = 4, Y = 4 
Salida: 43 
 

Enfoque: use el enfoque codicioso para seleccionar los elementos que darán como resultado la suma máxima. Los siguientes pasos ayudarán a resolver este problema: 
 

• Ordene los pares de elementos según la diferencia absoluta, es decir , |A[i] – B[i]| en orden decreciente.
• Compara el valor de A[i] y B[i] , el que sea mayor suma ese valor a la suma .
• Disminuya X en uno si el elemento se elige de A[i]; de lo contrario, disminuya Y en uno.
• Imprime la suma al final.

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

#include <bits/stdc++.h>
using namespace std;
long long getMaximumSum(vector<int> a, vector<int>b, int n, int x, int y) {
        vector<vector<int> > v;
        long long tsum=0;
        for(int i=0;i<n;i++)
        {
            v.push_back({abs(a[i]-b[i]),a[i],b[i]});
        }
        sort(v.begin(),v.end(),greater<vector<int> >());
        for(int i=0;i<v.size();i++)
        {
            if(v[i][1]>v[i][2] && x>0)
            {
                tsum+=v[i][1];
                x--;
            }
            else if(v[i][1]<v[i][2] && y>0)
            {
                tsum+=v[i][2];
                y--;
            }
            else
            {
                tsum+=min(v[i][2],v[i][1]);  
            }
        }
        return tsum;
}
int main() {
    int x = 3, y = 2;
    vector<int> a= { 1, 2, 3, 4, 5 };
    vector<int> b= { 5, 4, 3, 2, 1 };
    int n = a.size();
    cout<<getMaximumSum(a, b, n, x, y);
    return 0;
}

// Java program to calculate the
// maximum sum obtained by making an
// Optimal selection of elements from two given arrays
 
import java.io.*;
import java.util.*;
import java.lang.*;
 
// User defined Pair class
class Pair {
    int x;
    int y;
 
    // Constructor
    public Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
 
// Class to define user defined comparator
class Compare {
 
    // Function to reverse the elements of an array
    static void reverseArray(Pair[] arr, int start, int end)
    {
 
        int tempx, tempy;
        while (start < end) {
            tempx = arr[start].x;
            tempy = arr[start].y;
            arr[start].x = arr[end].x;
            arr[start].y = arr[end].y;
            arr[end].x = tempx;
            arr[end].y = tempy;
            start++;
            end--;
        }
    }
 
    // Function to sort the pair according to the
    // absolute differences
    static Pair[] compare(Pair[] arr, int N)
    {
 
        // Comparator to sort the pair according to
        // the absolute differences
        Arrays.sort(arr, new Comparator<Pair>() {
            @Override
            public int compare(Pair p1, Pair p2)
            {
                return (Math.abs(p1.x - p1.y) - Math.abs(p2.x - p2.y));
            }
        });
 
        // To get in descending order
        reverseArray(arr, 0, N - 1);
        return arr;
    }
}
 
// Driver class
class GFG {
 
    // Function to calculate the
    // maximum possible sum obtained by making an
    // optimal selection elements from two given arrays
 
    static int getMaximumSum(int[] A, int[] B, int N,
                                        int X, int Y)
    {
        int num1, num2, sum = 0;
 
        // Making a single pair array having
        // arr[i] element as (Ai, Bi)
        Pair[] arr = new Pair[N];
        for (int i = 0; i < N; i++) {
            arr[i] = new Pair(A[i], B[i]);
        }
 
        // Sorting according to the absolute differences
        // in the decreasing order
        Compare obj = new Compare();
        obj.compare(arr, N);
 
        // Applying Greedy approach to make an optimal
        // selection
        for (int i = 0; i < N; i++) {
            num1 = arr[i].x;
            num2 = arr[i].y;
 
            // If A[i] > B[i]
            if (num1 > num2) {
 
                // If element from A can be picked
                if (X > 0) {
                    sum += num1;
                    X--;
                }
 
                // Insufficient X
                // Make a pick from B
                else if (Y > 0) {
                    sum += num2;
                    Y--;
                }
            }
 
            // If B[i] > A[i]
            else if (num2 > num1 && Y > 0) {
 
                // If element from B can be picked
                if (Y > 0) {
                    sum += num2;
                    Y--;
                }
 
                // Insufficient Y
                // Make a pick from A
                else {
                    sum += num1;
                    X--;
                }
            }
 
            // If A[i] = B[i]
            // Doesn't make a difference so any value
            //  can be picked
            else {
                sum += num1;
                if (X > 0) {
                    X--;
                }
                else if (Y > 0)
                    Y--;
            }
        }
        return sum;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int X = 3, Y = 2;
        int[] A = { 1, 2, 3, 4, 5 };
        int[] B = { 5, 4, 3, 2, 1 };
        int N = A.length;
        System.out.println(getMaximumSum(A, B, N, X, Y));
    }
}

<script>
// Javascript program for the above approach
 
function getMaximumSum( a, b, n, x, y) {
        let v=[];
        let tsum=0;
        for(let i=0;i<n;i++)
        {
            v.push([Math.abs(a[i]-b[i]),a[i],b[i]]);
        }
        v.sort();
        v.reverse();
        for(let i=0;i<v.length;i++)
        {
            if(v[i][1]>v[i][2] && x>0)
            {
                tsum+=v[i][1];
                x--;
            }
            else if(v[i][1]<v[i][2] && y>0)
            {
                tsum+=v[i][2];
                y--;
            }
            else
            {
                tsum+=Math.min(v[i][2],v[i][1]);
            }
        }
        return tsum;
}
 
// Driver Code
    let x = 3;
    let y = 2;
    let a= [ 1, 2, 3, 4, 5 ];
    let b= [ 5, 4, 3, 2, 1 ];
    let n = a.length;
    document.write(getMaximumSum(a, b, n, x, y));
 
// This program is contributed by Pushpesh Raj.
</script>

21

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