Maximice la suma de la array intercambiando como máximo elementos K con otra array

Dadas dos arrays A y B de tamaño N y un número entero K , la tarea es encontrar la suma máxima posible de la array A intercambiando como máximo K elementos con la array B.
Ejemplos:
 

Entrada: A[] = {2, 3, 4}, B[] = {6, 8, 5}, K = 1 
Salida: 15 
Explicación: 
Intercambiar A[0] y B[1]. Por lo tanto suma = 8 + 3 + 4 = 15. 
Entrada: A[] = {9, 7}, B[] = {5, 1}, K = 2 
Salida: 16 
Explicación: 
Dado que todos los elementos de la array A son mayores que los elementos de la array B, no se requieren intercambios. 
 

Acercarse: 
 

1. Ordena las arrays A y B en orden no decreciente. 
    
2. Itere la array A desde el principio y la array B desde el final, de modo que podamos intercambiar el elemento mínimo de la array A con el elemento máximo de la array B. 
    
3. Si el elemento de la array A es más pequeño que el de la array B, cámbielos. De lo contrario, rompa el bucle. 
    
4. Haga esto para la mayoría de los elementos K. 
    
5. Encuentre la suma de la array resultante A. 
    

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

// C++ implementation to find maximum
// sum of array A by swapping
// at most K elements with array B
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum sum
void maximumSum(int a[], int b[],
                int k, int n)
{
    int i, j;
    sort(a, a + n);
    sort(b, b + n);
 
    // If element of array a is
    // smaller than that of
    // array b, swap them.
    for (i = 0, j = n - 1; i < k;
         i++, j--) {
        if (a[i] < b[j])
            swap(a[i], b[j]);
        else
            break;
    }
 
    // Find sum of resultant array
    int sum = 0;
    for (i = 0; i < n; i++)
        sum += a[i];
    cout << sum << endl;
}
 
int main()
{
    int K = 1;
    int A[] = { 2, 3, 4 };
    int B[] = { 6, 8, 5 };
 
    int N = sizeof(A) / sizeof(A[0]);
 
    maximumSum(A, B, K, N);
    return 0;
}

// Java implementation to find maximum
// sum of array A by swapping
// at most K elements with array B
import java.util.*;
class GFG{
 
// Function to find the maximum sum
static void maximumSum(int a[], int b[],
                       int k, int n)
{
    int i, j;
    Arrays.sort(a);
    Arrays.sort(b);
 
    // If element of array a is
    // smaller than that of
    // array b, swap them.
    for (i = 0, j = n - 1; i < k; i++, j--)
    {
        if (a[i] < b[j])
        {
            int temp = a[i];
            a[i] = b[j];
            b[j] = temp;
        }
        else
            break;
    }
 
    // Find sum of resultant array
    int sum = 0;
    for (i = 0; i < n; i++)
        sum += a[i];
    System.out.print(sum +"\n");
}
 
// Driver Code
public static void main(String[] args)
{
    int K = 1;
    int A[] = { 2, 3, 4 };
    int B[] = { 6, 8, 5 };
 
    int N = A.length;
 
    maximumSum(A, B, K, N);
}
}
 
// This code is contributed by sapnasingh4991

# Python3 implementation to find maximum
# sum of array A by swapping
# at most K elements with array B
 
# Function to find the maximum sum
def maximumSum(a, b, k, n):
 
    a.sort()
    b.sort()
 
    # If element of array a is
    # smaller than that of
    # array b, swap them.
    i = 0
    j = n - 1
     
    while i < k:
        if (a[i] < b[j]):
            a[i], b[j] = b[j], a[i]
             
        else:
            break
             
        i += 1
        j -= 1
 
    # Find sum of resultant array
    sum = 0
    for i in range (n):
        sum += a[i]
         
    print(sum)
 
# Driver code
if __name__ == "__main__":
     
    K = 1
    A = [ 2, 3, 4 ]
    B = [ 6, 8, 5 ]
 
    N = len(A)
 
    maximumSum(A, B, K, N)
 
# This code is contributed by chitranayal

// C# implementation to find maximum
// sum of array A by swapping
// at most K elements with array B
using System;
class GFG{
 
// Function to find the maximum sum
static void maximumSum(int []a,
                       int []b,
                       int k, int n)
{
    int i, j;
    Array.Sort(a);
    Array.Sort(b);
 
    // If element of array a is
    // smaller than that of
    // array b, swap them.
    for (i = 0, j = n - 1; i < k; i++, j--)
    {
        if (a[i] < b[j])
        {
            int temp = a[i];
            a[i] = b[j];
            b[j] = temp;
        }
        else
            break;
    }
 
    // Find sum of resultant array
    int sum = 0;
    for (i = 0; i < n; i++)
        sum += a[i];
    Console.Write(sum +"\n");
}
 
// Driver Code
public static void Main()
{
    int K = 1;
    int []A = { 2, 3, 4 };
    int []B = { 6, 8, 5 };
 
    int N = A.Length;
 
    maximumSum(A, B, K, N);
}
}
 
// This code is contributed by Code_Mech

<script>
// JavaScript implementation to find maximum
// sum of array A by swapping
// at most K elements with array B
 
 
// Function to find the maximum sum
function maximumSum(a, b, k, n)
{
    let i, j;
    a.sort();
    b.sort();
 
    // If element of array a is
    // smaller than that of
    // array b, swap them.
    for (i = 0, j = n - 1; i < k;
        i++, j--) {
        if (a[i] < b[j])
     {
       let temp = a[i];
       a[i] = b[j];
       b[j] = temp;
     }
        else
            break;
    }
 
    // Find sum of resultant array
    let sum = 0;
    for (i = 0; i < n; i++)
        sum += a[i];
    document.write(sum);
}
 
    let K = 1;
    let A = [2, 3, 4 ];
    let B = [ 6, 8, 5 ];
 
    let N = A.length;
 
    maximumSum(A, B, K, N);
     
// This code is contributed by vaibhavrabadiya117.
</script>

15

Análisis de rendimiento: 
 

• Complejidad de tiempo: O(N * log N)
• Espacio Auxiliar: O(1)