欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間:2022年09月14日 09:22:49   作者:AnjaVon  
這篇文章主要為大家介紹了Java C++ 題解leetcode857雇傭K名工人最低成本vector pair示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

題目要求

思路:優(yōu)先隊(duì)列 + 貪心

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;
    }
}
  • 時(shí)間復(fù)雜度:O(n log ?n)
  • 空間復(fù)雜度:O(n)

C++

學(xué)習(xí)了一下vectorpair的相互套用,以及自定義排序等內(nèi)容。

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;
    }
};
  • 時(shí)間復(fù)雜度:O(n log ?n)
  • 空間復(fù)雜度: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
    }
}
  • 時(shí)間復(fù)雜度:O(n log? n)
  • 空間復(fù)雜度:O(n)

以上就是Java C++ 題解leetcode857雇傭K名工人最低成本vector pair的詳細(xì)內(nèi)容,更多關(guān)于Java C++ vector pair的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • C語言中g(shù)etchar的用法以及實(shí)例解析

    C語言中g(shù)etchar的用法以及實(shí)例解析

    getchar()是stdio.h中的庫函數(shù),它的作用是從stdin流中讀入一個(gè)字符,下面這篇文章主要給大家介紹了關(guān)于C語言中g(shù)etchar的用法以及實(shí)例的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2022-03-03
  • C語言中的putchar函數(shù)示例

    C語言中的putchar函數(shù)示例

    putchar函數(shù)函數(shù)幾乎是在整個(gè)C語言中最沒有知名度的,它常常被程序員冷漠地對待,這篇文章主要介紹了C語言中的putchar函數(shù),需要的朋友可以參考下
    2022-12-12
  • c/c++拷貝構(gòu)造函數(shù)和關(guān)鍵字explicit詳解

    c/c++拷貝構(gòu)造函數(shù)和關(guān)鍵字explicit詳解

    這篇文章主要介紹了c/c++拷貝構(gòu)造函數(shù)和關(guān)鍵字explicit的相關(guān)知識,非常不錯(cuò),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2018-08-08
  • VC++ 自定義控件的建立及使用方法

    VC++ 自定義控件的建立及使用方法

    這篇文章主要介紹了VC++ 自定義控件的建立及使用方法的相關(guān)資料,十分的詳細(xì),需要的朋友可以參考下
    2015-06-06
  • linux c模擬ls命令詳解

    linux c模擬ls命令詳解

    本篇文章是對linux中基于c模擬ls命令的實(shí)現(xiàn)方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-06-06
  • C語言實(shí)現(xiàn)飛機(jī)訂票系統(tǒng)的完整代碼

    C語言實(shí)現(xiàn)飛機(jī)訂票系統(tǒng)的完整代碼

    為了免去在窗口排隊(duì)買票的麻煩,飛機(jī)訂票系統(tǒng)應(yīng)運(yùn)而生,下面這篇文章主要給大家介紹了關(guān)于C語言實(shí)現(xiàn)飛機(jī)訂票系統(tǒng)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2022-06-06
  • C語言遞歸實(shí)現(xiàn)線索二叉樹

    C語言遞歸實(shí)現(xiàn)線索二叉樹

    這篇文章主要介紹了C語言遞歸實(shí)現(xiàn)線索二叉樹,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2017-10-10
  • C++利用Socket實(shí)現(xiàn)主機(jī)間的UDP/TCP通信

    C++利用Socket實(shí)現(xiàn)主機(jī)間的UDP/TCP通信

    這篇文章主要為大家詳細(xì)介紹了C++如何利用Socket實(shí)現(xiàn)主機(jī)間的UDP/TCP通信功能,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下
    2023-01-01
  • Qt編程實(shí)現(xiàn)小時(shí)鐘

    Qt編程實(shí)現(xiàn)小時(shí)鐘

    這篇文章主要為大家詳細(xì)介紹了Qt編程實(shí)現(xiàn)小時(shí)鐘,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-05-05
  • VS2019開發(fā)簡單的C/C++動(dòng)態(tài)鏈接庫并進(jìn)行調(diào)用的實(shí)現(xiàn)

    VS2019開發(fā)簡單的C/C++動(dòng)態(tài)鏈接庫并進(jìn)行調(diào)用的實(shí)現(xiàn)

    這篇文章主要介紹了VS2019開發(fā)簡單的C/C++動(dòng)態(tài)鏈接庫并進(jìn)行調(diào)用的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-03-03

最新評論