Java C++ 题解leetcode857雇佣K名工人最低成本vector pair

题目要求思路：优先队列 + 贪心Java class Solution {public double mincostToHireWorkers(int[] qu

题目要求

思路：优先队列 + 贪心

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(n log ⁡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(n log ⁡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
    }
}