Назначьте стойла K коровам, чтобы максимально увеличить минимальное расстояние между ними.

Опубликовано: 25 Февраля, 2023

Дан отсортированный массив arr[] , состоящий из N целых чисел , обозначающих положение киоска. Вам также дано целое число K , обозначающее количество агрессивных коров. Вам дается задача распределить стойла для K коров так, чтобы минимальное расстояние между любыми двумя из них было максимально возможным.

Примеры:

Input: N = 5, K = 3, arr[] = {1, 2, 4, 8, 9}
Output: 3
Explanation: We can place cow 1 at position 1, cow 2 at position 4 and cow 3 at position 9. So, the maximum possible minimum distance between two cows is 3.

Input: N = 6, K = 4, arr[] = {6, 7,  9, 11, 13, 15}
Output: 2
Explanation: We can place cow 1 at position 6, cow 2 at position 9 and  cow 4 at position 15. So, the maximum possible minimum distance between two cows is 2.

Наивный подход: основной способ решения проблемы заключается в следующем:

The maximum distance possible between two cows can be the difference between the maximum and minimum element (Which is less than the maximum element of the array) of the array and the minimum possible distance can be 1.

Следуйте инструкциям, чтобы решить проблему:

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

Иллюстрация:

Consider: N = 5, K = 3, arr =  {1, 2, 4, 8, 9}.

  • Maximum element = 9. So we will iterate between 1 to 9.
  • At i = 1, we can place the cows at positions 1, 2, 4 maintaining the minimum distance of 1.
  • At i = 2, we can place the cows at positions 1, 4, 8 maintaining the minimum distance of 2.
  • At i = 3, we can place the cows at 1, 4, and 8 maintaining the minimum distance of 3.
  • At i = 4, we can not place the cows by maintaining the minimum distance of 4.
  • So, the largest possible distance is 3.

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

Временная сложность: O (N * (максимальный элемент во входном массиве))
Вспомогательное пространство: O(1).

Эффективный подход: в приведенном выше подходе поиск ответа можно оптимизировать с помощью двоичного поиска.

As we have seen in the case of brute force solution we are iterating from 1 to the maximum element of the array and at each distance, we check whether it can be our possible answer or not. Instead of doing this, we can run a binary search from 1 to the maximum element of the array.

Следуйте инструкциям, чтобы решить проблему:

  • Примените бинарный поиск между 1 и максимальным элементом массива.
    • Каждый раз находите средний элемент пространства поиска.
    • Если этот средний элемент может быть возможным минимальным расстоянием, сохраните его как возможность, пока мы не найдем лучший ответ, а затем двигайтесь в правильном направлении в пространстве поиска.
    • В противном случае мы будем двигаться влево в нашем пространстве поиска.
  • Когда бинарный поиск завершится, верните ответ.

Иллюстрация:

Consider: N = 5, K =3, arr =  {1, 2, 4, 8, 9}.

  • Maximum element = 9. So our search space will be 1 to 9.
  • First, L = 1 and R = 9, mid = 5; we can not place the cows by maintaining the minimum distance of 5. So, we will move left in our search space.
  • Now, L = 1 and R = 4, mid = 2; we can place the cows at positions 1, 4, and 8 maintaining the minimum distance of 2. So, we will store 2 as a possible answers and move right into our search space.
  • Now, L=3 and R=4, mid = 3; we can place the cows at positions 1, 4, and 8 maintaining the minimum distance of 3. So, we will store 3 as a possible answers and move right into our search space.
  • Now, L = 4 and R = 4, mid = 4; we can not place the cows by maintaining the minimum distance of 5. So, we will move left in our search space.
  • Now, L = 4 and R = 3, Since, L > R, our binary search is complete, and the largest possible answer is 3.

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

Временная сложность: O (N * log (максимальный элемент массива))
Вспомогательное пространство: O(1)

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