每日一题做题记录，参考官方和三叶的题解

题目要求

思路：优先队列 + 贪心

• 这个比例有点难搞，所以就假设结果中工资与能力的比值为ratioratioratio，根据工资需满足其对应wage[i]wage[i]wage[i]的条件可知ratio≥wage[i]quality[i]ratio\ge \frac{wage[i]}{quality[i]}ratio≥quality[i]wage[i]​。
• 要保证每个人的工资合法且成本最低，那么实际结果的ratioratioratio要尽可能小，但是被选择的kkk个人中最大的。
• 那么就把每个人的ratioratioratio计算出来排序，然后依次枚举将其作为结果比例判断是否合法。
  • ratioratioratio为二维的，第一个变量记录当前员工的比例，第二个变量记录其工作量。
  • 判断合法的过程引入优先队列，用大根堆记录当前所选择的工人，并利用其性质（超出人数，将工作量最大的排除）更新当前的最低成本。
    • 工作量大者，将拉低整体工资，为保证成本低而工资高，要保证工作量总和较小。
  • 用变量tottottot记录当前的总工作量，根据当前枚举的ratioratioratio更新成本。

Java

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        double[][] ratio = new double[n][2];
        for (int i = 0; i < n; i++) {
            ratio[i][0] = wage[i] * 1.0 / quality[i];
            ratio[i][1] = quality[i] * 1.0;
        }
        Arrays.sort(ratio, (a, b) -> Double.compare(a[0], b[0]));
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        double res = 1e18;
        for (int i = 0, tot = 0; i < n; i++) {
            int cur = (int) ratio[i][1];
            tot += cur;
            pq.add(cur);
            if (pq.size() > k)
                tot -= pq.poll();
            if (pq.size() == k)
                res = Math.min(res, tot * ratio[i][0]);
        }
        return res;
    }
}

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)
• 空间复杂度：O(n)O(n)O(n)

C++

• 学习了一下vector和pair的相互套用，以及自定义排序等内容。

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        int n = quality.size();
        vector<pair<double, int>> ratio;
        for (int i = 0; i < n; i++) {
            ratio.emplace_back(wage[i] * 1.0 / quality[i], quality[i]);
        }
        sort(ratio.begin(), ratio.end(), [](const pair<double, int> &a, const pair<double, int> &b) {
            return a.first < b.first;
        });
        priority_queue<int> pq;
        double res = 1e18;
        for (int i = 0, tot = 0; i < n; i++) {
            int cur = ratio[i].second;
            tot += cur;
            pq.emplace(cur);
            if (pq.size() > k) {
                tot -= pq.top();
                pq.pop();
            }
                
            if (pq.size() == k)
                res = min(res, tot * ratio[i].first);
        }
        return res;
    }
};

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)
• 空间复杂度：O(n)O(n)O(n)

Rust

use std::collections::BinaryHeap;
impl Solution {
    pub fn mincost_to_hire_workers(quality: Vec<i32>, wage: Vec<i32>, k: i32) -> f64 {
        let (mut res, mut tot, mut pq) = (f64::MAX, 0, BinaryHeap::new());
        let mut ratio = quality.iter().zip(wage.iter()).map(|(q, w)| (*w as f64 / *q as f64, *q as f64)).collect::<Vec<_>>();
        ratio.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
        for (a, b) in ratio {
            tot += b as i32;
            pq.push(b as i32);
            if pq.len() as i32 > k {
                tot -= pq.pop().unwrap();
            }
            if pq.len() as i32 == k {
                res = res.min(a * tot as f64);
            }
        }
        res
    }
}

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)
• 空间复杂度：O(n)O(n)O(n)

总结

看到困难就可以直接去找题解了【不是】，看完题想到了应该要用堆，但是确实没想出来咋用，乖乖学习题解。

但懂了但没完全懂的感觉，下次遇到应该会持续懵逼……

回来又搞了一搞，基本弄明白了，发现之前的代码有点问题也订正了~

欢迎指正与讨论！