雇佣 K 名工人的最低成本

/*
 * Problem: Given n workers, each worker has a certain quality and a minimum expected wage. 
 * We want to hire k workers such that we minimize the total amount of money paid. 
 * We must pay each worker based on the ratio of their quality to other workers' quality, 
 * and each worker must receive at least their minimum expected wage.
 * 
 * Solution Approach: 
 * 1. Calculate the ratio of wage[i] / quality[i] for each worker and sort them by this ratio.
 * 2. Use a priority queue to maintain the smallest k quality workers.
 * 3. For each worker, calculate the total wage needed if they are the highest ratio worker.
 * 4. Track the minimum total wage.
 */

import java.util.*;
import java.util.stream.*;

public class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        // Create a list of Worker objects and sort by the ratio of wage/quality
        List<Worker> workers = IntStream.range(0, quality.length)
                .mapToObj(i -> new Worker(quality[i], wage[i]))
                .sorted(Comparator.comparingDouble(worker -> worker.ratio))
                .collect(Collectors.toList());

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        double totalQuality = 0.0;
        double result = Double.MAX_VALUE;
        // Iterate through workers and maintain the smallest k quality workers
        for (Worker worker : workers) {
            totalQuality += worker.quality;
            maxHeap.add(worker.quality);
            if (maxHeap.size() > k) {
                totalQuality -= maxHeap.poll();
            }
            if (maxHeap.size() == k) {
                result = Math.min(result, totalQuality * worker.ratio);
            }
        }
        return result;
    }

    class Worker {
        int quality;
        int wage;
        double ratio;

        Worker(int quality, int wage) {
            this.quality = quality;
            this.wage = wage;
            this.ratio = (double) wage / quality;
        }
    }
}