Dadas tres arrays a[] , b[] y c[] de tamaños A , B y C respectivamente, la tarea es encontrar el valor mínimo posible de abs(a[i] – b[j]) + abs(b[ j] – c[k]) donde 0 ≤ yo ≤ UN , 0 ≤ j ≤ segundo y 0 ≤ k ≤ C .
Ejemplos:
Entrada: A = 3, B = 2, C = 2, a[] = {1, 8, 5}, b[] = {2, 9}, c[] = {5, 4}
Salida: 3
Explicación:
El triplete (a[0], b[0], c[1]), es decir (1, 2, 4) tiene la suma mínima de la diferencia absoluta de pares, es decir abs(1 – 2) + abs(2 – 4) = 1 + 2 = 3.Entrada: A = 4, B = 3, C = 3, a[] = {4, 5, 1, 7}, b[] = {8, 5, 6}, c[] = {2, 7, 12 }
Salida: 2
Explicación:
El triplete (a[1], b[1], c[1]), es decir, (1, 5, 7) tiene una suma mínima de diferencia absoluta de pares, es decir, abs(5 – 5) + abs(5 – 7) = 0 + 2 = 2.
Enfoque: La idea para resolver este problema es ordenar los arreglos a[] y c[] y luego atravesar el arreglo b[] y encontrar los elementos que satisfacen la condición dada.
Siga los pasos a continuación para resolver el problema:
- Inicialice la variable, digamos min , como INT_MAX , para almacenar el valor mínimo posible.
- Ordena las arrays a[] y c[] en orden creciente.
- Recorra la array b[] y para cada elemento, digamos b[i] , encuentre el elemento más cercano a b[i] de las arrays a[] y c[] como arr_close y crr_close y haga lo siguiente:
- Para encontrar el elemento más cercano, primero encuentre el límite inferior del elemento de destino b[i] .
- Si se encuentra el límite inferior, compruebe si es el primer elemento de la array o no. Si no es así, compare el límite inferior y su elemento anterior con el elemento de destino y encuentre cuál está más cerca del elemento de destino.
- Si no se encuentra el límite inferior, el elemento más cercano será el último elemento de la array.
- Actualice min como el mínimo de abs(b[i] – arr_close) + abs(b[i] – crr_close) .
- Después de completar los pasos anteriores, imprima el valor de min como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to find the value
// closest to K in the array A[]
int closestValue(vector<int> A, int k)
{
// Initialize close value as the
// end element
int close = A.back();
// Find lower bound of the array
auto it = lower_bound(A.begin(),
A.end(), k);
// If lower_bound is found
if (it != A.end()) {
close = *it;
// If lower_bound is not
// the first array element
if (it != A.begin()) {
// If *(it - 1) is closer to k
if ((k - *(it - 1))
< (close - k)) {
close = *(it - 1);
}
}
}
// Return closest value of k
return close;
}
// Function to find the minimum sum of
// abs(arr[i] - brr[j]) and abs(brr[j]-crr[k])
void minPossible(vector<int> arr,
vector<int> brr,
vector<int> crr)
{
// Sort the vectors arr and crr
sort(arr.begin(), arr.end());
sort(crr.begin(), crr.end());
// Initialize minimum as INT_MAX
int minimum = INT_MAX;
// Traverse the array brr[]
for (int val : brr) {
// Stores the element closest
// to val from the array arr[]
int arr_close = closestValue(arr, val);
// Stores the element closest
// to val from the array crr[]
int crr_close = closestValue(crr, val);
// If sum of differences is minimum
if (abs(val - arr_close)
+ abs(val - crr_close)
< minimum)
// Update the minimum
minimum = abs(val - arr_close)
+ abs(val - crr_close);
}
// Print the minimum absolute
// difference possible
cout << minimum;
}
// Driver Code
int main()
{
vector<int> a = { 1, 8, 5 };
vector<int> b = { 2, 9 };
vector<int> c = { 5, 4 };
// Function Call
minPossible(a, b, c);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Lower_bound function
public static int lower_bound(int arr[], int key)
{
int low = 0;
int high = arr.length - 1;
while (low < high)
{
int mid = low + (high - low) / 2;
if (arr[mid] >= key)
{
high = mid;
}
else
{
low = mid + 1;
}
}
return low;
}
// Function to find the value
// closest to K in the array A[]
static int closestValue(int A[], int k)
{
// Initialize close value as the
// end element
int close = A[A.length - 1];
// Find lower bound of the array
int it = lower_bound(A, k);
// If lower_bound is found
if (it != A.length)
{
close = A[it];
// If lower_bound is not
// the first array element
if (it != 0)
{
// If *(it - 1) is closer to k
if ((k - A[it - 1]) < (close - k))
{
close = A[it - 1];
}
}
}
// Return closest value of k
return close;
}
// Function to find the minimum sum of
// abs(arr[i] - brr[j]) and abs(brr[j]-crr[k])
static void minPossible(int arr[], int brr[],
int crr[])
{
// Sort the vectors arr and crr
Arrays.sort(arr);
Arrays.sort(crr);
// Initialize minimum as INT_MAX
int minimum = Integer.MAX_VALUE;
// Traverse the array brr[]
for(int val : brr)
{
// Stores the element closest
// to val from the array arr[]
int arr_close = closestValue(arr, val);
// Stores the element closest
// to val from the array crr[]
int crr_close = closestValue(crr, val);
// If sum of differences is minimum
if (Math.abs(val - arr_close) +
Math.abs(val - crr_close) < minimum)
// Update the minimum
minimum = Math.abs(val - arr_close) +
Math.abs(val - crr_close);
}
// Print the minimum absolute
// difference possible
System.out.println(minimum);
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 1, 8, 5 };
int b[] = { 2, 9 };
int c[] = { 5, 4 };
// Function Call
minPossible(a, b, c);
}
}
// This code is contributed by Kingash
Python3
# Python program to implement # the above approach # Lower_bound function def lower_bound(arr, key): low = 0; high = len(arr) - 1; while (low < high): mid = low + (high - low) // 2; if (arr[mid] >= key): high = mid; else: low = mid + 1; return low; # Function to find the value # closest to K in the array A[] def closestValue(A, k): # Initialize close value as the # end element close = A[-1]; # Find lower bound of the array it = lower_bound(A, k); # If lower_bound is found if (it != len(A)): close = A[it]; # If lower_bound is not # the first array element if (it != 0): # If *(it - 1) is closer to k if ((k - A[it - 1]) < (close - k)): close = A[it - 1]; # Return closest value of k return close; # Function to find the minimum sum of # abs(arr[i] - brr[j]) and abs(brr[j]-crr[k]) def minPossible(arr, brr, crr): # Sort the vectors arr and crr arr.sort(); crr.sort(); # Initialize minimum as LET_MAX minimum = 10**9; # Traverse the array brr[] for val in brr: # Stores the element closest # to val from the array arr[] arr_close = closestValue(arr, val); # Stores the element closest # to val from the array crr[] crr_close = closestValue(crr, val); # If sum of differences is minimum if (abs(val - arr_close) + abs(val - crr_close) < minimum): # Update the minimum minimum = abs(val - arr_close) + abs(val - crr_close); # Print the minimum absolute # difference possible print(minimum); # Driver code a = [ 1, 8, 5 ]; b = [ 2, 9 ]; c = [ 5, 4 ]; # Function Call minPossible(a, b, c); # This code is contributed by gfgking
C#
// C# program for the above approach
using System;
class GFG{
// Lower_bound function
public static int lower_bound(int[] arr, int key)
{
int low = 0;
int high = arr.Length - 1;
while (low < high)
{
int mid = low + (high - low) / 2;
if (arr[mid] >= key)
{
high = mid;
}
else
{
low = mid + 1;
}
}
return low;
}
// Function to find the value
// closest to K in the array A[]
static int closestValue(int []A, int k)
{
// Initialize close value as the
// end element
int close = A[A.Length - 1];
// Find lower bound of the array
int it = lower_bound(A, k);
// If lower_bound is found
if (it != A.Length)
{
close = A[it];
// If lower_bound is not
// the first array element
if (it != 0)
{
// If *(it - 1) is closer to k
if ((k - A[it - 1]) < (close - k))
{
close = A[it - 1];
}
}
}
// Return closest value of k
return close;
}
// Function to find the minimum sum of
// abs(arr[i] - brr[j]) and abs(brr[j]-crr[k])
static void minPossible(int[] arr, int[] brr,
int[] crr)
{
// Sort the vectors arr and crr
Array.Sort(arr);
Array.Sort(crr);
// Initialize minimum as INT_MAX
int minimum = Int32.MaxValue;
// Traverse the array brr[]
foreach(int val in brr)
{
// Stores the element closest
// to val from the array arr[]
int arr_close = closestValue(arr, val);
// Stores the element closest
// to val from the array crr[]
int crr_close = closestValue(crr, val);
// If sum of differences is minimum
if (Math.Abs(val - arr_close) +
Math.Abs(val - crr_close) < minimum)
// Update the minimum
minimum = Math.Abs(val - arr_close) +
Math.Abs(val - crr_close);
}
// Print the minimum absolute
// difference possible
Console.WriteLine(minimum);
}
// Driver Code
static void Main()
{
int []a = { 1, 8, 5 };
int []b = { 2, 9 };
int []c = { 5, 4 };
// Function Call
minPossible(a, b, c);
}
}
// This code is contributed by SoumikMondal
Javascript
<script>
// JavaScript program to implement
// the above approach
// Lower_bound function
function lower_bound(arr, key)
{
let low = 0;
let high = arr.length - 1;
while (low < high)
{
let mid = low + Math.floor((high - low) / 2);
if (arr[mid] >= key)
{
high = mid;
}
else
{
low = mid + 1;
}
}
return low;
}
// Function to find the value
// closest to K in the array A[]
function closestValue(A, k)
{
// Initialize close value as the
// end element
let close = A[A.length - 1];
// Find lower bound of the array
let it = lower_bound(A, k);
// If lower_bound is found
if (it != A.length)
{
close = A[it];
// If lower_bound is not
// the first array element
if (it != 0)
{
// If *(it - 1) is closer to k
if ((k - A[it - 1]) < (close - k))
{
close = A[it - 1];
}
}
}
// Return closest value of k
return close;
}
// Function to find the minimum sum of
// abs(arr[i] - brr[j]) and abs(brr[j]-crr[k])
function minPossible(arr, brr, crr)
{
// Sort the vectors arr and crr
arr.sort();
crr.sort();
// Initialize minimum as LET_MAX
let minimum = Number.MAX_VALUE;
// Traverse the array brr[]
for(let val in brr)
{
// Stores the element closest
// to val from the array arr[]
let arr_close = closestValue(arr, val);
// Stores the element closest
// to val from the array crr[]
let crr_close = closestValue(crr, val);
// If sum of differences is minimum
if (Math.abs(val - arr_close) +
Math.abs(val - crr_close) < minimum)
// Update the minimum
minimum = Math.abs(val - arr_close) +
Math.abs(val - crr_close);
}
// Print the minimum absolute
// difference possible
document.write(minimum);
}
// Driver code
let a = [ 1, 8, 5 ];
let b = [ 2, 9 ];
let c = [ 5, 4 ];
// Function Call
minPossible(a, b, c);
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
3
Complejidad de tiempo: O(A*log A + C*log C+ B*log A + B*log C)
Espacio auxiliar: O(A + B + C)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA