Daily LeetCode – day0044 0857. Minimum Cost to Hire K Workers

import java.util.Arrays;
import java.util.PriorityQueue;

// 0857. Minimum Cost to Hire K Workers
class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int len = quality.length;
        Worker[] workers = new Worker[len];
        for (int i = 0; i < len; ++i) {
            workers[i] = new Worker(quality[i], wage[i]);
        }
        Arrays.sort(workers, (Worker w1, Worker w2) -> (int) ((w1.costEffective - w2.costEffective) * 100000));
        PriorityQueue<Worker> pq = new PriorityQueue<>((Worker w1, Worker w2) -> w2.quality - w1.quality);
        long sumQuality = 0;
        for (int i = 0; i < k; ++i) {
            sumQuality += workers[i].quality;
            pq.offer(workers[i]);
        }
        double ans = sumQuality * workers[k - 1].costEffective;
        for (int i = k; i < len; ++i) {
            if (workers[i].quality < pq.peek().quality) {
                sumQuality -= pq.poll().quality;
                sumQuality += workers[i].quality;
                pq.offer(workers[i]);
                if (sumQuality * workers[i].costEffective < ans) {
                    ans = sumQuality * workers[i].costEffective;
                }
            }
        }
        return ans;
    }
}

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

    public Worker(int quality, int wage) {
        this.quality = quality;
        this.wage = wage;
        this.costEffective = wage * 1.0 / quality;
    }
}

学习笔记：
今天来当一个黑心资本家。
这是一道优先队列、排序的困难题。
先要进行排序，排序就是按照性价比的方式来排，然后维护一个优先队列，把干活多的放顶上，先踢出干活多的，然后看看能不能降低成本。