Максимальное произведение суммы скоростей K рабочих и их минимальной эффективности.
Даны целое число 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) = 60Input: 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)