Максимальное количество пар, при которых элемент с каждым индексом i входит в i пар

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

Дан массив arr[] и целое число N , задача состоит в том, чтобы найти максимальное количество пар, которые могут быть сформированы таким образом, что i -й индекс входит в почти arr[i] пары.

Примеры:

Input: arr[] = {2, 2, 3, 4} 
Output: 
5
1 3
2 4
2 4
3 4
3 4
Explanation: For the given array, a maximum of 5 pairs can be created where 1st index is included in 1 pair, 2nd index in 2 pairs, 3rd index in 3 pairs and 4th index in 4 pairs as shown above. 

Input: arr[] = {8, 2, 0, 1, 1}
Output: 
4
1 2
1 5
1 4
1 2

Подход: Данную задачу можно решить с помощью жадного подхода. Можно заметить, что наиболее оптимальным выбором на каждом этапе является выберите элементы с максимальным значением и создайте их соответствующую пару. Используя это наблюдение, выполните следующие шаги, чтобы решить эту проблему:

  • Создайте очередь с максимальным приоритетом, в которой индексы данного массива хранятся в порядке убывания их соответствующего значения массива.
  • Создайте цикл для повторения приоритетной очереди до тех пор, пока в ней не будет более двух элементов, и выполните следующие шаги:
    • Выберите два верхних индекса в очереди приоритетов, добавьте их пару в массив ответов.
    • Повторно вставьте их в очередь приоритетов после уменьшения их соответствующих значений массива, если их значения больше 0.
  • Выведите все пары в массиве ответов.

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


Временная сложность: O(M*log M), где M обозначает сумму всех элементов массива.
Вспомогательное пространство: O(N)

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