Минимизируйте значение уравнения (yi + yj + |xi – xj|), используя заданные точки

Опубликовано: 20 Сентября, 2022

Дан массив arr[] размера N , где arr[i] имеет форму [xi , yi], обозначающую точку (xi , yi) на двумерной плоскости. Массив отсортирован по x-координатам. Кроме того, дано целое число K. Задача состоит в том, чтобы минимизировать значение уравнения y i + y j + |x i – x j | где |x i – x j | ≤ K и 1 ≤ я < j ≤ N . Гарантируется, что существует хотя бы одна пара точек, удовлетворяющих ограничению |x i – x j | ≤ К.

Примеры:

Input: arr[4] = {{1, 3}, {2, 0}, {5, 10}, {6, -10}}, K = 1
Output: 1
Explanation: The first two points satisfies the given condition |xi – xj| ≤ 1. 
Now, the equation  =  3 + 0 + |1 – 2| = 4. 
Similarly, Third and fourth points also satisfy the condition and 
give a value of 10 + -10 + |5 – 6| = 1. 
Except these 2 pairs no other points satisfy the given condition. 
Minimum of 4 and 1 is 1. So output is 1.

Input: arr[4] = {{0, 0}, {3, 0}, {9, 2}}, K = 3
Output: 3
Explanation: Only the first two points have an absolute difference of 3. 
It gives the value of 0 + 0 + |0 – 3| = 3.

Подход: Задача сводится к поиску минимального значения (y j + x j ) + (y i – x i ) . Поскольку абсолютная разность координат x рассматриваемых точек должна быть меньше или равна K , задача может быть решена с использованием минимальной кучи. Для каждой точки рассмотрите верхнее значение кучи и проверьте, меньше ли координата x вершины и текущей точки, чем K , возьмите минимум среди них и обновите кучу и выполните то же самое для остальных координат. Выполните следующие шаги, чтобы решить эту проблему:

  • Инициализировать очередь с минимальным приоритетом minh[].
  • Инициализируйте переменную min_val как INT_MAX .
  • Перебрать диапазон [0, n), используя индекс переменной, и выполнить следующие задачи:
    • Выталкивайте элементы из min-кучи minh[] до тех пор, пока разница в координатах x не превысит K .
    • Если куча не пуста, обновите значение min_val.
    • Нажмите значение {arr[index][1] – arr[index][0], arr[index][0]}.
  • После выполнения вышеуказанных шагов выведите значение min_val в качестве ответа.

Ниже приведена реализация описанного выше подхода.


Временная сложность: O(NlogN)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ