Minimice la suma de las diferencias absolutas de los mismos elementos indexados de dos arrays dadas como máximo con un reemplazo

Dadas dos arrays A[] y B[] de tamaño N cada una, la tarea es encontrar la suma mínima posible de la diferencia absoluta de los mismos elementos indexados de las dos arrays, es decir, la suma de |A[i] – B[i]| para todo i tal que 0 ≤ i < N reemplazando como máximo un elemento en A[] con otro elemento de A[] .

Ejemplos:

Entrada: A[] = {6, 4, 1, 9, 7, 5}, B[] = {3, 9, 7, 4, 2, 1}, N = 6
Salida: 22
Explicación: Reemplazar A[2 ] con A[4]. La array A[] se modifica a [6, 4, 7, 9, 7, 5]. Esto produce una diferencia de suma absoluta de |6 – 3| + |4 – 9| + |7 – 7| + |9 – 4| + |7 – 2| + |5 – 1| = 22, que es el máximo posible.

Entrada: A[] = {2, 5, 8}, B[] = {7, 6, 1}, N = 3
Salida: 7

Enfoque: La idea para resolver el problema es calcular para cada B[i] (0 ≤ i < N) , el elemento más cercano en A[] a B[i] mediante la búsqueda binaria y elegir la mejor opción. 
Siga los pasos a continuación para resolver el problema.

1. Inicialice dos arrays diff[] y BestDiff[] de tamaño N .
2. Inicializar una suma variable a 0 .
3. Recorra de 0 a N – 1 y para cada i almacene diff[i]= abs(A[i] – B[i]) y agregue diff[i] a sum .
4. Ordene la array A[] en orden ascendente.
5. Iterar sobre los índices 0 a N – 1 y para cada i , usando la búsqueda binaria , encuentre el elemento en A[] que esté más cerca de B[i] , diga X y guárdelo en BestDiff[] como BestDiff[i] = abs (B[i] – X)
6. Inicialice una variable BestPick .
7. Iterar sobre los índices 0 a N – 1 y actualizar BestPick como BestPick = max(BestPick, diff[i]-BestDiff[i])
8. Ahora, Sum – BestPick da la respuesta.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return minimum sum of absolute
// difference of same-indexed elements of two arrays
int minAbsoluteSumDiff(vector<int> A,
                       vector<int> B, int N)
{
    // Stores initial sum
    int sum = 0;
 
    // Stores the differences between
    // same-indexed elements of A[] and B[]
    int diff[N];
 
    for (int i = 0; i < N; i++) {
 
        // Update absolute difference
        diff[i] = abs(A[i] - B[i]);
 
        // Update sum of differences
        sum += diff[i];
    }
 
    // Sort array A[] in ascending order
    sort(A.begin(), A.end());
 
    // Stores best possible
    // difference for each i
    int bestDiff[N];
 
    for (int i = 0; i < N; i++) {
 
        // Find the index in A[]
        // which >= B[i].
        int j = lower_bound(A.begin(), A.end(), B[i])
                - A.begin();
 
        // Store minimum of abs(A[j] - B[i])
        // and abs(A[j - 1] - B[i])
        if (j != 0 && j != N)
            bestDiff[i] = min(abs(A[j] - B[i]),
                              abs(A[j - 1] - B[i]));
 
        // If A[j] can be replaced
        else if (j == 0)
            bestDiff[i] = abs(A[j] - B[i]);
 
        // If A[j - 1] can be replaced
        else if (j == N)
            bestDiff[i] = abs(A[j - 1] - B[i]);
    }
 
    // Find best possible replacement
    int bestPick = 0;
    for (int i = 0; i < N; i++) {
        bestPick = max(bestPick,
                       diff[i] - bestDiff[i]);
    }
 
    // Return the result
    return sum - bestPick;
}
 
// Driver code
int main()
{
    // Input
    vector<int> A = { 2, 5, 8 };
    vector<int> B = { 7, 6, 1 };
 
    int N = 3;
 
    cout << minAbsoluteSumDiff(A, B, N) << endl;
 
    return 0;
}

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Recursive implementation of
    // lower_bound
    static int lower_bound(int arr[], int low, int high,
                           int X)
    {
 
        // Base Case
        if (low > high) {
            return low;
        }
 
        // Find the middle index
        int mid = low + (high - low) / 2;
 
        // If arr[mid] is greater than
        // or equal to X then search
        // in left subarray
        if (arr[mid] >= X) {
            return lower_bound(arr, low, mid - 1, X);
        }
 
        // If arr[mid] is less than X
        // then search in right subarray
        return lower_bound(arr, mid + 1, high, X);
    }
 
    // Function to return minimum sum of absolute
    // difference of same-indexed elements of two arrays
    static int minAbsoluteSumDiff(int A[], int B[], int N)
    {
        // Stores initial sum
        int sum = 0;
 
        // Stores the differences between
        // same-indexed elements of A[] and B[]
        int diff[] = new int[N];
 
        for (int i = 0; i < N; i++) {
 
            // Update absolute difference
            diff[i] = Math.abs(A[i] - B[i]);
 
            // Update sum of differences
            sum += diff[i];
        }
 
        // Sort array A[] in ascending order
        Arrays.sort(A);
 
        // Stores best possible
        // difference for each i
        int bestDiff[] = new int[N];
 
        for (int i = 0; i < N; i++) {
 
            // Find the index in A[]
            // which >= B[i].
            int j = lower_bound(A, 0, N - 1, B[i]);
 
            // Store minimum of abs(A[j] - B[i])
            // and abs(A[j - 1] - B[i])
            if (j != 0 && j != N)
                bestDiff[i]
                    = Math.min(Math.abs(A[j] - B[i]),
                               Math.abs(A[j - 1] - B[i]));
 
            // If A[j] can be replaced
            else if (j == 0)
                bestDiff[i] = Math.abs(A[j] - B[i]);
 
            // If A[j - 1] can be replaced
            else if (j == N)
                bestDiff[i] = Math.abs(A[j - 1] - B[i]);
        }
 
        // Find best possible replacement
        int bestPick = 0;
        for (int i = 0; i < N; i++) {
            bestPick
                = Math.max(bestPick, diff[i] - bestDiff[i]);
        }
 
        // Return the result
        return sum - bestPick;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Input
        int A[] = { 2, 5, 8 };
        int B[] = { 7, 6, 1 };
 
        int N = 3;
 
        System.out.println(minAbsoluteSumDiff(A, B, N));
    }
}
 
// This code is contributed by Dharanendra L V.

# Python3 program for the above approach
from bisect import bisect_left,bisect_right
 
# Function to return minimum sum of absolute
# difference of same-indexed elements of two arrays
def minAbsoluteSumDiff(A, B, N):
     
    # Stores initial sum
    sum = 0
 
    # Stores the differences between
    # same-indexed elements of A[] and B[]
    diff = [0] * N
 
    for i in range(N):
 
        # Update absolute difference
        diff[i] = abs(A[i] - B[i])
 
        # Update sum of differences
        sum += diff[i]
     
    # Sort array A[] in ascending order
    A.sort()
 
    # Stores best possible
    # difference for each i
    bestDiff = [0] * N
 
    for i in range(N):
 
        # Find the index in A[]
        # which >= B[i].
        j = bisect_left(A, B[i])
           
        # Store minimum of abs(A[j] - B[i])
        # and abs(A[j - 1] - B[i])
        if (j != 0 and j != N):
            bestDiff[i] = min(abs(A[j] - B[i]),
                              abs(A[j - 1] - B[i]))
 
        # If A[j] can be replaced
        elif (j == 0):
            bestDiff[i] = abs(A[j] - B[i])
 
        # If A[j - 1] can be replaced
        elif (j == N):
            bestDiff[i] = abs(A[j - 1] - B[i])
    
    # Find best possible replacement
    bestPick = 0
     
    for i in range(N):
        bestPick = max(bestPick,
                       diff[i] - bestDiff[i])
 
    # Return the result
    return sum - bestPick
 
# Driver code
if __name__ == "__main__":
   
    # Input
    A = [ 2, 5, 8 ]
    B = [ 7, 6, 1 ]
 
    N = 3
 
    print(minAbsoluteSumDiff(A, B, N))
     
# This code is contributed by ukasp

// C# program for the above approach
using System;
 
class GFG {
 
    // Recursive implementation of
    // lower_bound
static int lower_bound(int []arr, int low, int high, int X)
    {
 
        // Base Case
        if (low > high) {
            return low;
        }
 
        // Find the middle index
        int mid = low + (high - low) / 2;
 
        // If arr[mid] is greater than
        // or equal to X then search
        // in left subarray
        if (arr[mid] >= X) {
            return lower_bound(arr, low, mid - 1, X);
        }
 
        // If arr[mid] is less than X
        // then search in right subarray
        return lower_bound(arr, mid + 1, high, X);
    }
 
    // Function to return minimum sum of absolute
    // difference of same-indexed elements of two arrays
    static int minAbsoluteSumDiff(int []A, int []B, int N)
    {
        // Stores initial sum
        int sum = 0;
 
        // Stores the differences between
        // same-indexed elements of A[] and B[]
        int []diff = new int[N];
 
        for (int i = 0; i < N; i++) {
 
            // Update absolute difference
            diff[i] = Math.Abs(A[i] - B[i]);
 
            // Update sum of differences
            sum += diff[i];
        }
 
        // Sort array A[] in ascending order
        Array.Sort(A);
 
        // Stores best possible
        // difference for each i
        int []bestDiff = new int[N];
 
        for (int i = 0; i < N; i++) {
 
            // Find the index in A[]
            // which >= B[i].
            int j = lower_bound(A, 0, N - 1, B[i]);
 
            // Store minimum of abs(A[j] - B[i])
            // and abs(A[j - 1] - B[i])
            if (j != 0 && j != N)
                bestDiff[i]
                    = Math.Min(Math.Abs(A[j] - B[i]),
                               Math.Abs(A[j - 1] - B[i]));
 
            // If A[j] can be replaced
            else if (j == 0)
                bestDiff[i] = Math.Abs(A[j] - B[i]);
 
            // If A[j - 1] can be replaced
            else if (j == N)
                bestDiff[i] = Math.Abs(A[j - 1] - B[i]);
        }
 
        // Find best possible replacement
        int bestPick = 0;
        for (int i = 0; i < N; i++) {
            bestPick
                = Math.Max(bestPick, diff[i] - bestDiff[i]);
        }
 
        // Return the result
        return sum - bestPick;
    }
 
    // Driver code
    public static void Main()
    {
        // Input
        int []A = { 2, 5, 8 };
        int []B = { 7, 6, 1 };
 
        int N = 3;
 
        Console.Write(minAbsoluteSumDiff(A, B, N));
    }
}
 
// This code is contributed by ipg2016107.

<script>
 
// JavaScript program for the above approach
 
 
  function lower_bound(arr, low, high,
                           X)
    {
 
        // Base Case
        if (low > high) {
            return low;
        }
 
        // Find the middle index
        var mid = low + (high - low) / 2;
 
        // If arr[mid] is greater than
        // or equal to X then search
        // in left subarray
        if (arr[mid] >= X) {
            return lower_bound(arr, low, mid - 1, X);
        }
 
        // If arr[mid] is less than X
        // then search in right subarray
        return lower_bound(arr, mid + 1, high, X);
    }
 
    // Function to return minimum sum of absolute
    // difference of same-indexed elements of two arrays
    function minAbsoluteSumDiff(A, B, N)
    {
        // Stores initial sum
        var sum = 0;
 
        // Stores the differences between
        // same-indexed elements of A[] and B[]
        var diff = new Array(N);
 
        for (i = 0; i < N; i++) {
 
            // Update absolute difference
            diff[i] = Math.abs(A[i] - B[i]);
 
            // Update sum of differences
            sum += diff[i];
        }
 
        // Sort array A[] in ascending order
        A.sort();
 
        // Stores best possible
        // difference for each i
        var bestDiff = new Array(N);
        var i;
        for (i = 0; i < N; i++) {
 
            // Find the index in A[]
            // which >= B[i].
            var j = lower_bound(A, 0, N - 1, B[i]);
 
            // Store minimum of abs(A[j] - B[i])
            // and abs(A[j - 1] - B[i])
            if (j != 0 && j != N)
                bestDiff[i]
                    = Math.min(Math.abs(A[j] - B[i]),
                               Math.abs(A[j - 1] - B[i]));
 
            // If A[j] can be replaced
            else if (j == 0)
                bestDiff[i] = Math.abs(A[j] - B[i]);
 
            // If A[j - 1] can be replaced
            else if (j == N)
                bestDiff[i] = Math.abs(A[j - 1] - B[i]);
        }
 
        // Find best possible replacement
        var bestPick = 0;
        for (i = 0; i < N; i++) {
            bestPick
                = Math.max(bestPick, diff[i] - bestDiff[i]);
        }
 
        // Return the result
        return sum - bestPick;
    }
 
         // Driver code
        // Input
        var A = [2, 5, 8];
        var B = [7, 6, 1];
 
        var N = 3;
 
        document.write(minAbsoluteSumDiff(A, B, N));
 
</script>

7

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