雇用K工人的最低成本


难度级别
经常问 谷歌

在雇用K工人的最低成本问题中,我们给了N个工人,我们希望从这些N工人中确切地雇用k工人来组成一个有薪群体。 第i个工人具有质量[i]和最低工资期望工资[i]。

他们将按照以下规则支付报酬:

  1. 与该付费组中的其他工人相比,该付费组中的每个工人都应按其质量的比率获得报酬。
  2. 带薪组中的每个工人都必须至少获得其最低工资期望。

使用案列

输入: 质量= [50,30,10,60,70],工资= [100,120,130,90,140],K = 3

输出: 360

雇用K工人的最低成本的要点

假设我们有,质量= [a,b,c,d],工资= [p,q,r,s]

  • 相对于第一要素的有效质量比为: [1,b / a,c / a,d / a]
  • 有效工资为:[p,pb / a,pc / a,pd / a]
  • 确保 最低工资 当考虑第j个元素的比例时,通过选择第i个元素,形成一个由k个工人组成的有薪工作组:B [i] <=(A [i] / A [j])* B [j] == B [i] / A [i] <= B [j] / A [j]即,为了满足条件,应按降序排列质量/最低工资的比率,并且随后的第j个工人的比率在考虑时将自动满足最低工资条件第ith个元素。
  • 对于 最佳解决方案:说(b / cr + r + d / cr)等于写作:(b + c + d)*(r / c),即,质量的最小总和乘以比例因子即可。 我们已经有R / c降序O(nlogn)。
  • 从第nk-1个元素开始,意味着从第(nk)个元素的角度来看,最后k个元素是最小可用元素。 保持这些数字的最大堆(-最小堆==最大堆)。 如我们所见,该数字小于最小k个元素的最大值:我们只是删除了最大值,然后插入了新元素。
  • 一旦检测到新的较小元素:更新堆并检查新的潜在最小总和。

雇用K工人的最低成本的实施

C ++程序

#include<bits/stdc++.h>
using namespace std;
double hireKworkers(vector<int>& quality, vector<int>& wage, int K) {
    int N = quality.size();
    vector<pair<double, int>> vec;
    for(int i = 0; i < N; i++) {
        vec.push_back(make_pair(wage[i] * 1.0 / quality[i], quality[i])); 
    } 
    sort(vec.begin(), vec.end(), [](auto& a, auto& b){
        return a.first < b.first;
    });
    int quality_cnt = 0;
    priority_queue<int> q;
    for(int i = 0; i < K; i++) {
        quality_cnt += vec[i].second;
        q.push(vec[i].second);
    }
    double ans = quality_cnt * vec[K - 1].first;
    for(int i = K; i < N; i++) {
        q.push(vec[i].second);
        quality_cnt += vec[i].second;
        quality_cnt -= q.top();
        q.pop();
        ans = min(ans, quality_cnt * vec[i].first);
    }
    return ans;
}

int main(){
    int n=5;
    vector<int> quality ={50, 30, 10, 60, 70};
    vector<int> wages = {100, 120, 130, 90, 140};
    int k=3;
    cout<<"The least amount of money needed to form a paid group: "<<hireKworkers(quality,wages,k);
}
The least amount of money needed to form a paid group: 360

JAVA程序

import java.util.*;
class Main { 
    public static double hireKworkers(int[] quality, int[] wage, int K) {
        double[][] workers = new double[quality.length][2];
        PriorityQueue<Double> heap = new PriorityQueue<>(Comparator.reverseOrder());
        double sum = 0;
        double result = Integer.MAX_VALUE;
        for(int i = 0; i < quality.length; i++) {
            workers[i][0] = (double) wage[i] / (double) quality[i];
            workers[i][1] = quality[i];
        }
        Arrays.sort(workers, (o1, o2) -> {
            if(o1[0] - o2[0] == 0) return 0;
            if(o1[0] - o2[0] > 0) return 1;
            return -1;
        });
        for(double[] worker : workers) {
            if(heap.size() == K) {
                sum -= heap.poll();
            }
            heap.add(worker[1]);
            sum += worker[1];
            if(heap.size() == K) {
                result = Math.min(result, sum * worker[0]);
            }
        }
        return result;
    }

  
    public static void main(String args[]) 
    { 
        int n=4;
        int[] quality = { 20, 40, 10, 50};
        int[] wages = {70, 80, 30, 40};
        int k=3;
        System.out.println("The least amount of money needed to form a paid group: "+hireKworkers(quality,wages,k));
    } 
}
The least amount of money needed to form a paid group: 245.0

雇用K工人的最低成本的复杂性分析

时间复杂度

O(NlogN) 插入堆/优先级队列需要花费登录时间,我们正在遍历整个 排列 因此,一次的总时间复杂度将为O(NlogN)

空间复杂度

上) 其中N是输入数组的大小。

參考資料