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

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

Даны два массива arr[] и powr[] размера N и целое число K . Каждый элемент arr[i] имеет соответствующую мощность powr[i] . Задача состоит в том, чтобы максимизировать значение заданной функции, выбрав не более чем K элементов из массива. Функция определяется как:

f(N) = (arr[i1] + arr[i2] + arr[i3]+…..arr[in]) * min(powr[i1], powr[i2], powr[i3], …..powr[in]) where, arr[i1], arr[i2], arr[i3], …..arr[in] are the chosen elements.

Примеры:

Input: arr[] = {11, 10, 7, 6, 9}, powr[] = {3, 2, 4, 1, 1}, K = 2, N = 5 
Output: 54
Explanation: Choose elements at indices {0, 2} so, f(N) = (11 + 7) * min(3, 4) = 18 * 3 = 54, which is the maximum possible value that can be achieved by choosing at most 2 elements.

Input: arr[] = {5, 12, 11, 9}, powr[] = {2, 1, 10, 1}, K = 3, N = 4 
Output: 110

Подход: Идея состоит в том, чтобы рассматривать каждый i -й элемент как минимальную мощность, для этого отсортировать элементы в порядке убывания мощности, так что первый элемент будет считаться имеющим наибольшую мощность. Всегда старайтесь поддерживать список элементов размером не более K . Этот список будет содержать не более K элементов с самым большим , не включая текущий i -й элемент. Если у вас уже есть список размером K , удалите элемент с наименьшей длиной, чтобы size стал K – 1 , затем включите текущий элемент в список, size станет K , и обновите res до максимального значения. В конце верните res , который является ответом.

  • Инициализируйте вектор пар v[] размера N для хранения элементов вместе с их мощностью.
  • Перебрать диапазон [0, N), используя переменную i , и выполнить следующие задачи:
    • Присвойте значения power[i] и arr[i] в качестве первого и второго значений массива v[].
  • Отсортируйте массив v[] по возрастанию.
  • Инициализируйте переменные res и sum как 0 , чтобы сохранить результат и сумму.
  • Инициализировать набор пар s[] .
  • Переберите диапазон [N-1, 0], используя переменную i , и выполните следующие задачи:
    • Вставьте пару {v[i].second, i} в набор s[].
    • Добавьте значение v[i].second к переменной sum.
    • Если s.size() больше K , выполните следующие задачи:
      • Инициализируйте переменную it как первый элемент набора s[].
      • Уменьшите значение it.first из переменной sum.
      • Удалите переменную it из множества s[].
    • Установите значение res как максимальное значение res или sum*v[i].first.
  • После выполнения вышеуказанных шагов выведите значение res в качестве ответа.

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

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

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