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

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

Даны целое число N , представляющее количество рабочих, массив speed[ ] , где speed[i] представляет скорость i -го работника, и массив efficiency[ ] , где efficiency[i] представляет собой эффективность i -го работника. рабочего и целое число K , задача состоит в том, чтобы выбрать K рабочих так, чтобы (Сумма скоростей всех рабочих) * (Минимальная эффективность среди K рабочих) была максимально возможной.

Примеры:

Input: N = 6, speed[] = {2, 10, 3, 1, 5, 8}, efficiency[] = {5, 4, 3, 9, 7, 2}, K = 2
Output: 60
Explanation: 
Selecting 2nd worker (Speed = 10 and Efficiency = 4) and 5th worker ( Speed = 5 and Efficiency = 7). 
Therefore, the maximum sum possible = (10 + 5) * min(4, 7) = 60

Input: N = 6, speed[] = {2, 10, 3, 1, 5, 8}, efficiency[] = {5, 4, 3, 9, 7, 2}, K = 3
Output: 68

Подход: выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте вектор пар arr[ ] , где arr[i] равно {efficiency[i], speed[i]} размера N .
  • Отсортируйте arr[ ] в порядке убывания эффективности.
  • Инициализировать min priority_queue, в котором хранится скорость воркеров.
  • Инициализируйте переменные, скажем, SumOfSpeed = 0 и Ans = 0 .
  • Переберите arr[ ] и сделайте следующее:
    • Добавьте arr[i].first в SumOfSpeed.
    • Нажмите speed[i] в priority_queue.
    • Если размер priority_queue превышает K, извлеките переднюю часть priority_queue и вычтите из SumOfSpeed .
    • Обновите Ans как максимальное значение Ans и SumOfSpeed * efficiency[i] .
  • Наконец, верните Ans .

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


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

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