Dada una array 2D ordenada arr[][2] de tamaño N tal que (arr[i][0], arr[i][1]) representa las coordenadas del i -ésimo punto en el plano cartesiano y un número entero K , el tarea es encontrar el valor máximo de la expresión (|arr[i][0]– arr[j][0]| + arr[i][1]+ arr[j][1]) tal que |arr[ i][0]– arr[j][0]| ≤ K para cualquier posible par de coordenadas (i, j).
Ejemplos:
Entrada: arr[][] = {{1, 3}, {2, 0}, {5, 10}, {6, -10}}, K = 1
Salida: 4
Explicación:
Elija pares (0, 1) . Ahora el valor de la expresión viene dado por:
valor = (abs(1 – 2) + 3 + 0) = 4, que es máximo y abs(1 – 2) = 1(≤ K).
Por lo tanto, imprime 4.Entrada: arr[][] = {{0, 0}, {3, 0}, {9, 2}}, K = 3
Salida: 3
Enfoque: el problema dado se puede resolver utilizando un algoritmo codicioso utilizando la cola de prioridad que se basa en las siguientes observaciones:
- Reordenando la expresión para todo i > j como (arr[i][0]– arr[i][1]+ arr[j][0]+ arr[j][1]) .
- Ahora, manteniendo el par de {arr[i] x – arr[i] y , arr[i] x } en orden ordenado, se puede calcular el valor de la expresión dada para cada elemento del arreglo en el índice j .
Siga los pasos a continuación para resolver el problema:
- Inicialice una cola de prioridad de pares, digamos PQ , que almacena el par de diferencias de los ejes coordinados de un punto y la coordenada X de ese punto.
- Inicialice una variable, digamos res como INT_MIN para almacenar el valor máximo.
- Atraviese la array arr[][] y teniendo en cuenta que {X, Y} es el punto actual, realice las siguientes operaciones:
- Iterar mientras PQ no está vacío y (X – PQ.top()[1]) es mayor que K y eliminar el elemento superior de la cola de prioridad PQ .
- Si PQ no está vacío, actualice el valor de res como el máximo de res y PQ.top()[0] + X + Y) .
- Empuje el par {Y – X, X} en la cola de prioridad PQ .
- Después de completar los pasos anteriores, imprima el valor de res como resultado.
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; // Function to find the maximum value // of the given expression possible // for any pair of co-ordinates void findMaxValueOfEquation( vector<vector<int> >& arr, int K) { // Stores the differences between pairs priority_queue<vector<int> > pq; // Stores the maximum value int res = INT_MIN; // Traverse the array arr[][] for (auto point : arr) { // While pq is not empty and // difference between point[0] // and pq.top()[1] > K while (!pq.empty() && point[0] - pq.top()[1] > K) { // Removes the top element pq.pop(); } // If pq is not empty if (!pq.empty()) { // Update the value res res = max(res, pq.top()[0] + point[0] + point[1]); } // Push pair {point[1] - point[0], // point[0]} in pq pq.push({ point[1] - point[0], point[0] }); } // Print the result cout << res; } // Driver Code int main() { vector<vector<int> > arr = { { 1, 3 }, { 2, 0 }, { 5, 10 }, { 6, -10 } }; int K = 1; findMaxValueOfEquation(arr, K); return 0; }
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; public class GFG { // Function to find the maximum value // of the given expression possible // for any pair of co-ordinates static void findMaxValueOfEquation(int arr[][], int K) { // Stores the differences between pairs PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> { if (a[0] != b[0]) return b[0] - a[0]; return b[1] - a[1]; }); // Stores the maximum value int res = Integer.MIN_VALUE; // Traverse the array arr[][] for (int point[] : arr) { // While pq is not empty and // difference between point[0] // and pq.top()[1] > K while (!pq.isEmpty() && point[0] - pq.peek()[1] > K) { // Removes the top element pq.poll(); } // If pq is not empty if (!pq.isEmpty()) { // Update the value res res = Math.max(res, pq.peek()[0] + point[0] + point[1]); } // Push pair {point[1] - point[0], // point[0]} in pq pq.add(new int[] { point[1] - point[0], point[0] }); } // Print the result System.out.println(res); } // Driver Code public static void main(String[] args) { int[][] arr = { { 1, 3 }, { 2, 0 }, { 5, 10 }, { 6, -10 } }; int K = 1; findMaxValueOfEquation(arr, K); } } // This code is contributed by Kingash.
Python3
# Python3 program for the above approach # Function to find the maximum value # of the given expression possible # for any pair of co-ordinates def findMaxValueOfEquation(arr, K): # Stores the differences between pairs pq = [] # Stores the maximum value res = -10**8 # Traverse the array arr[][] for point in arr: # While pq is not empty and # difference between point[0] # and pq.top()[1] > K while (len(pq)>0 and point[0] - pq[-1][1] > K): # Removes the top element del pq[-1] # If pq is not empty if (len(pq) > 0): # Update the value res res = max(res, pq[-1][0] + point[0] + point[1]) # Push pair {point[1] - point[0], # point[0]} in pq pq.append([point[1] - point[0], point[0]]) pq = sorted(pq) # Print the result print (res) # Driver Code if __name__ == '__main__': arr = [ [ 1, 3 ], [ 2, 0 ], [ 5, 10 ], [ 6, -10 ] ] K = 1 findMaxValueOfEquation(arr, K) # This code is contributed by mohit kumar 29.
Javascript
<script> // Javascript program for the above approach // Function to find the maximum value // of the given expression possible // for any pair of co-ordinates function findMaxValueOfEquation(arr,K) { // Stores the differences between pairs let pq=[]; // Stores the maximum value let res = Number.MIN_VALUE; // Traverse the array arr[][] for (let point=0;point< arr.length;point++) { // While pq is not empty and // difference between point[0] // and pq.top()[1] > K while (pq.length!=0 && arr[point][0] - pq[0][1] > K) { // Removes the top element pq.shift(); } // If pq is not empty if (pq.length!=0) { // Update the value res res = Math.max(res, pq[0][0] + arr[point][0] + arr[point][1]); } // Push pair {point[1] - point[0], // point[0]} in pq pq.push([ arr[point][1] - arr[point][0], arr[point][0] ]); pq.sort(function(a,b){ if (a[0] != b[0]) return b[0] - a[0]; return b[1] - a[1];}) } // Print the result document.write(res); } // Driver Code let arr = [[ 1, 3 ], [ 2, 0 ], [ 5, 10 ], [ 6, -10 ]]; let K = 1; findMaxValueOfEquation(arr, K); // This code is contributed by unknown2108 </script>
4
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por TanmayChakraborty y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA