题目分析

想要求解本题，首先要明白本题的意思，理解题意的时间可能比求解本题还要困难。题意是说每个人都有一个工作质量quality，如果一个人的工作质量是另一个人的两倍，那么他的工资也至少是他的两倍，且要满足最低工资。

堆

我们发现，如果薪水除以工作质量，可以得到时薪

如果两个人的时薪一样，那么两个人的工资一定是一样的。
如果时薪A > B，那么A和B共同选择的时候，支付的钱是按照时薪贵的来算。

以例题来算，第一个工人A的工作质量为10，薪水为70，因此时薪为7元，第三个工人C的工作质量为5，薪水为30，因此时薪为6元。如果按照C的时薪，则第一个人薪水应该发60元，低于70元，不满足条件。因此只能按照A的时薪来算，因为A的时薪高于C，因此折算到C的工作质量，薪水一定高于B

因为W[A] / Q[A] > W[C] / Q[C]，所以W[A] / Q[A] x Q[C] > W[C]。

所以按照A的时薪计算出来的结果，一定大于B的期望薪水。所以总花费是(A的工作质量 + B的工作质量) x A的时薪。

所以我们可以从小到大枚举时薪，并使用最大堆存放工作质量，当有一名新的工人被挑选时，时薪肯定会增加，但是工作质量可能会降低(从堆中pop一个最大的工作质量，添加了此名工人的工作质量)，因此计算出来的结果可能会变小。

算法的**时间复杂度为O(nlog(n))，空间复杂度为O(n)**。

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        int[][] combine = new int[n][2];
        for (int i = 0; i < n; i++) {
            combine[i][0] = quality[i];
            combine[i][1] = wage[i];
        }
        Arrays.sort(combine, (o1, o2) -> o1[1] * o2[0] - o2[1] * o1[0]);
        double cnt = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        double res = 1e13;
        for (int i = 0; i < k; i++) {
            cnt += combine[i][0];
            queue.add(combine[i][0]);
        }
        res = Math.min(res, cnt * combine[k - 1][1] / combine[k - 1][0]);
        for (int i = k; i < n; i++) {
            if (combine[i][0] < queue.peek()) {
                cnt -= queue.poll();
                cnt += combine[i][0];
                queue.add(combine[i][0]);
                res = Math.min(res, cnt * combine[i][1] / combine[i][0]);
            }
        }
        return res;
    }
}

刷题总结

堆是很常用的数据结构，当看到最值时，一定不要忘记它，能够在log(n)的时间复杂度内帮你找到当前集合中的最值。