Максимизируйте среднее значение отношений N пар с шагом M

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

Примеры:

Input: arr[] = {{1, 2}, {3, 5}, {2, 2}}, M = 2
Output: 0.783333
Explanation:
Below are the operations performed:
Operation 1: Increment the first and second element of pair {1, 2} by 1. Now, the array modifies to {{2, 3}, {3, 5}, {2, 2}}.
Operation 2: Increment the first and second element of pair {2, 3} by 1. Now, the array modifies to {{3, 4}, {3, 5}, {2, 2}}.
After the above operations, the average of the ratio of the pairs is ((3/4) + (3/5) + (2/2))/3 = 0.7833 which is the maximum possible.

Input: arr[] = {{2, 5}, {3, 5}}, M = 3
Output: 0.619048

Подход: Данную проблему можно решить, сохранив увеличение отношения, применив операцию к парам с использованием Max-heap, а затем продолжая извлекать значения M раз из кучи и добавлять к общей сумме. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте приоритетную очередь, скажем, PQ пар, чтобы сохранить соответствующее изменение в среднем и индекс пары, если к ней применяется одна операция.
• Инициализируйте переменную, скажем, sum как 0 , чтобы сохранить максимальное среднее соотношение пар.
• Пройдите по заданному массиву пар arr[] и найдите увеличение отношения после добавления 1 к обоим значениям пары и поместите значение в приоритетную очередь PQ . Также добавьте отношение i ^-й пары к переменной sum .
• Повторяйте, пока значение M не станет положительным, и выполните следующие шаги:
  • Извлеките верхний элемент приоритетной очереди PQ и добавьте увеличение отношения к сумме .
  • Обновите значение этой пары и поместите новое увеличение отношения пары в приоритетную очередь PQ .
• После выполнения вышеуказанных шагов выведите в качестве результата значение суммы , деленной на N.

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

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