Максимальное количество взрывов бомб, которое может произойти, прежде чем вор будет пойман

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

Дан массив arr[] из M целых чисел, где i -й элемент представляет время, по истечении которого i -я бомба взорвется после ее сброса, и три целых числа N, X и Y , представляющие количество смежных непрерывных ячеек в X -координата и начальные позиции ячейки вора и полиции. Задача состоит в том, чтобы найти максимальное количество взрывов бомб, которое может произойти до того, как вор будет пойман, если каждую секунду вор может либо сбросить бомбу, либо переместиться влево или вправо от существующей камеры, не посещаемой полицией.

Примеры:

Input: arr[] = {1, 4}, N = 7, X = 3, Y = 6
Output: 2
Explanation: 
One possible way is:

  1. At t = 0: Thief drops the bomb of activating time equal to 4. Meanwhile, the police move one cell towards the thief. Thereafter, the positions of the thief and police are 3 and 5 respectively.
  2. At t = 1: The police move one cell towards the thief and the thief moves one cell to its left. Thereafter, the positions of the thief and police are 2 and 4 respectively.
  3. At t = 2: The police move one cell towards the thief and the thief moves one cell to its left. Thereafter, the positions of the thief and police are 1 and 3 respectively.
  4. At t = 3: The police move one cell towards the thief and the thief drops the bomb of activating time equal to 1. Thereafter, the positions of the thief and police are 1 and 2 respectively.
  5. At t = 4: The bombs dropped at time (t= 3, and t = 0) blasts. Now the thief cannot move to any cell, and it does not have any bombs left. The police move one cell towards the thief, finally catching it at cell 1.

Therefore, the maximum bomb blasts that occurred before the thief got caught is 2.

Input: arr[] = {5, 1}, N = 7, X = 3, Y = 6
Output: 1

Подход: Данная проблема может быть решена на основе следующих наблюдений:

  1. Если и полицейский, и вор двигаются оптимально, то каждую секунду полицейский будет приближаться к вору. Таким образом, максимальное время, которое есть у вора, прежде чем его поймают, равно расстоянию между его позициями.
  2. Можно заметить, что лучший выбор — сначала сбросить бомбу с большим временем активации, чем с меньшим временем активации. Если сначала сбросить бомбу с меньшим временем, а затем сбросить бомбу с большим временем активации, это может превысить время, которое есть у вора, прежде чем его поймают.

Выполните следующие шаги, чтобы решить проблему:

  • Отсортируйте массив arr[] по убыванию.
  • Инициализируйте две переменные, скажем, count и time со значением 0 , чтобы сохранить максимальное количество взрывов бомб, которые могут произойти, и прошедшее время.
  • Найдите абсолютную разницу между X и Y и сохраните ее в переменной, скажем, maxSec .
  • Повторите в диапазоне [0, M-1] , используя переменную i , и выполните следующие шаги:
    • Если сумма текущего элемента и времени меньше или равна maxSec, тогда счетчик и время увеличиваются на 1 .
  • После вышеуказанного шага обновите счетчик как count = min(count, abs(XY)-1).
  • Наконец, после выполнения вышеуказанных шагов выведите значение count в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(M*log(M)), где M — размер массива arr[].
Вспомогательное пространство: O(1)

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