Задача: 857. Minimum Cost to Hire K Workers
Сложность: hard

Есть n работников. Вам даны два целочисленных массива: quality и wage, где quality[i] — качество работы i-го работника, а wage[i] — минимальная ожидаемая заработная плата i-го работника.

Мы хотим нанять ровно k работников для формирования оплачиваемой группы. Чтобы нанять группу из k работников, мы должны оплатить их в соответствии со следующими правилами:

Каждому работнику в оплачиваемой группе должно быть выплачено как минимум его ожидаемое минимальное вознаграждение.
В группе заработная плата каждого работника должна быть прямо пропорциональна его качеству. Это означает, что если качество работы одного работника вдвое выше, чем у другого работника в группе, то ему должно быть выплачено вдвое больше.
Учитывая целое число k, верните наименьшую сумму денег, необходимую для формирования оплачиваемой группы, удовлетворяющей указанным условиям. Ответы с точностью до 10^-5 от фактического ответа будут приняты.

Пример:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.

👨‍💻 Алгоритм:

1⃣Инициализируйте переменные: n для размера массивов quality и wage, totalCost для минимальной стоимости (начальное значение - максимум) и currentTotalQuality для суммы качеств текущих работников. Создайте массив wageToQualityRatio для хранения отношения заработной платы к качеству и качества каждого работника. Рассчитайте и сохраните отношение заработной платы к качеству для каждого работника в wageToQualityRatio. Отсортируйте wageToQualityRatio по возрастанию.

2⃣Создайте приоритетную очередь workers (максимальная куча) для хранения выбранных работников. Итерируйте через отсортированный wageToQualityRatio: добавляйте качество текущего работника в workers и обновляйте currentTotalQuality.

3⃣Если размер workers превышает k, удалите работника с наибольшим качеством из workers и обновите currentTotalQuality. Если размер workers равен k, рассчитайте общую стоимость, умножив currentTotalQuality на отношение заработной платы к качеству текущего работника. Обновите totalCost, если рассчитанная стоимость меньше текущей. Верните totalCost.

😎 Решение:

public class Solution {
    public double MincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.Length;
        double totalCost = double.MaxValue;
        double currentTotalQuality = 0;
        var wageToQualityRatio = new List<(double, int)>();

        for (int i = 0; i < n; i++) {
            wageToQualityRatio.Add(((double) wage[i] / quality[i], quality[i]));
        }

        wageToQualityRatio.Sort((a, b) => a.Item1.CompareTo(b.Item1));
        var workers = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));

        foreach (var (ratio, q) in wageToQualityRatio) {
            workers.Enqueue(q, q);
            currentTotalQuality += q;

            if (workers.Count > k) {
                currentTotalQuality -= workers.Dequeue();
            }

            if (workers.Count == k) {
                totalCost = Math.Min(totalCost, currentTotalQuality * ratio);
            }
        }

        return totalCost;
    }
}

Ставь 👍 и забирай 📚 Базу знаний