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

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

Примеры:

Input: arr[] = {4, 6}, M = 4
Output: 19
Explanation:
Below are the order of the product sell to gain the maximum profit:
Product 1: Sell a product from the second supplier, then the array modifies to {4, 5} and the profit is 6.
Product 2: Sell a product from the second supplier, then the array modifies to{4, 4} and the profit is 6 + 5 = 11.
Product 3: Sell a product from the second supplier, then the array modifies to {4, 3} and the profit is 6 + 5 + 4 = 15.
Product 4: Sell a product from the first supplier, then the array modifies to {3, 3} and the profit is 6 + 5 + 4 + 4 = 19.
Therefore, the maximum profit that can be obtained by selling 4 products is 19.

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

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать, используя Max-Heap для отслеживания максимального элемента в массиве за время O(log N) . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте Max-Heap, используя приоритетную очередь, скажем, Q , чтобы отслеживать максимальный элемент, присутствующий в массиве.
• Пройдите массив arr[] и вставьте все элементы в кучу Q .
• Инициализируйте переменную, скажем, maxProfit как 0 , чтобы сохранить результат максимальной полученной прибыли.
• Повторяйте цикл, пока M > 0 , и выполните следующие шаги:
  • Уменьшите значение M на 1 .
  • Сохраните значение верхнего элемента очереди приоритетов Q в переменной X и извлеките его из очереди приоритетов.
  • Добавьте значение X к переменной maxProfit и вставьте (X – 1) в переменную Q.
• После выполнения вышеуказанных шагов выведите в качестве результата значение maxProfit .

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

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