Dada una array arr[] de tamaño N donde arr[i] tiene la forma [x i , y i ] que denota un punto (x i , y i ) en un plano 2D. La array está ordenada en coordenadas x. Además, se da un número entero K. La tarea es minimizar el valor de la ecuación y i + y j + |x i – x j | donde |x i – x j | ≤ K y 1 ≤ yo < j ≤ norte. Se garantiza que existe al menos un par de puntos que satisfacen la restricción |x i – x j | ≤ k
Ejemplos:
Entrada: arr[4] = {{1, 3}, {2, 0}, {5, 10}, {6, -10}}, K = 1 Salida: 1 Explicación: Los primeros dos puntos
satisfacen la
condición dada |x yo – x j | ≤ 1.
Ahora, la ecuación = 3 + 0 + |1 – 2| = 4.
De manera similar, los puntos tercero y cuarto también satisfacen la condición y
dan un valor de 10 + -10 + |5 – 6| = 1.
Excepto estos 2 pares, ningún otro punto satisface la condición dada.
Mínimo de 4 y 1 es 1. Entonces la salida es 1.Entrada: arr[4] = {{0, 0}, {3, 0}, {9, 2}}, K = 3 Salida: 3
Explicación :
Solo los primeros dos puntos tienen una diferencia absoluta de 3.
Da la valor de 0 + 0 + |0 – 3| = 3.
Enfoque: El problema se reduce a encontrar el valor mínimo de (y j + x j ) + (y i – x i ) . Dado que la diferencia absoluta de las coordenadas x de los puntos considerados debe ser menor o igual a K , el problema se puede resolver utilizando un montón mínimo . Para todos y cada uno de los puntos, considere el valor superior del montón y verifique si la coordenada x de la parte superior y el punto actual es menor que K , tome el mínimo entre ellos y actualice el montón y siga lo mismo para el resto de las coordenadas. Siga los pasos a continuación para resolver este problema:
- Inicialice la cola de prioridad mínima minh[].
- Inicialice la variable min_val como INT_MAX .
- Iterar sobre el rango [0, n) usando el índice variable y realizar las siguientes tareas:
- Extraiga los elementos del min-heap minh[] hasta que la diferencia en las coordenadas x sea mayor que K .
- Si el montón no está vacío, actualice el valor de min_val.
- Introduzca el valor de {arr[índice][1] – arr[índice][0], arr[índice][0]}.
- Después de realizar los pasos anteriores, imprima el valor de min_val como respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
// Utility function to find minimum
// value of equation
int MinimumValue(int arr[][2], int n, int k)
{
// Minimum heap for storing
// (x-y) difference and x
// coordinate as the pair
priority_queue<pi, vector<pi>,
greater<pi> >
minh;
int min_val = INT_MAX;
for (int index = 0; index < n; index++) {
// Pop until the x-coordinates
// difference is greater than K
while ((
!minh.empty()
&& ((arr[index][0]
- minh.top().second)
> k))) {
minh.pop();
}
// If not heap empty update min_val
if (!minh.empty()) {
min_val
= min(min_val,
arr[index][0]
+ arr[index][1]
+ minh.top().first);
}
// Push the current pair in the heap
minh.push({ arr[index][1]
- arr[index][0],
arr[index][0] });
}
return min_val;
}
// Driver Code
int main()
{
// Input taken
int arr[4][2]
= { { 1, 3 }, { 2, 0 },
{ 5, 10 }, { 6, -10 } };
int K = 1;
int n = 4;
// Function called
cout << MinimumValue(arr, n, K) << "\n";
return 0;
}
Java
// Java program for the above approach
import java.util.PriorityQueue;
public class GFG
{
// Utility function to find minimum
// value of equation
static int MinimumValue(int[][] arr, int n, int k)
{
// Minimum heap for storing
// (x-y) difference and x
// coordinate as the pair
PriorityQueue<int[]> minh
= new PriorityQueue<int[]>((a, b) -> {
if (a[0] == b[0])
return a[1] - b[1];
return a[0] - b[0];
});
int min_val = Integer.MAX_VALUE;
for (int index = 0; index < n; index++)
{
// Pop until the x-coordinates
// difference is greater than K
while (!minh.isEmpty()) {
int[] pi = minh.poll();
if ((arr[index][0] - (-1 * pi[1])) <= k) {
minh.add(pi);
break;
}
}
// If not heap empty update min_val
if (!minh.isEmpty()) {
int[] pi = minh.poll();
min_val = Math.min(
min_val, arr[index][0] + arr[index][1]
+ (-1 * pi[1]));
minh.add(pi);
}
// Push the current pair in the heap
minh.add(new int[] { -1 * arr[index][1]
- (-1 * arr[index][0]),
-1 * arr[index][0] });
}
return min_val;
}
// Driver code
public static void main(String[] args)
{
// Input taken
int[][] arr
= { { 1, 3 }, { 2, 0 }, { 5, 10 }, { 6, -10 } };
int K = 1;
int n = 4;
// Function called
System.out.println(MinimumValue(arr, n, K));
}
}
// This code is contributed by Lovely Jain
Python3
# python3 program for the above approach from queue import PriorityQueue INT_MAX = 2147483647 # Utility function to find minimum # value of equation def MinimumValue(arr, n, k): # Minimum heap for storing # (x-y) difference and x # coordinate as the pair minh = PriorityQueue() min_val = INT_MAX for index in range(0, n): # Pop until the x-coordinates # difference is greater than K while (not minh.empty()): pi = minh.get() if((arr[index][0] - (-1*pi[1])) <= k): minh.put(pi) break # If not heap empty update min_val if (not minh.empty()): pi = minh.get() min_val = min(min_val, arr[index][0] + arr[index][1] + (-1*pi[1])) minh.put(pi) # Push the current pair in the heap minh.put([-1*arr[index][1] - (-1*arr[index][0]), -1*arr[index][0]]) return min_val # Driver Code if __name__ == "__main__": # Input taken arr = [[1, 3], [2, 0], [5, 10], [6, -10]] K = 1 n = 4 # Function called print(MinimumValue(arr, n, K)) # This code is contributed by rakeshsahni
1
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)