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