K 근로자를 고용하기위한 최소 비용

난이도 하드
자주 묻는 질문 구글
더미조회수 51

K 명의 근로자를 고용하기위한 최소 비용 문제에서, 우리는 정확히 k 명의 근로자를 고용하여 유급 그룹을 형성 할 N 명의 근로자를 제공했습니다. 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 번째 근로자는 고려시 자동으로 최저 임금 조건을 만족하게됩니다. i 번째 요소.
  • 다음 최적의 솔루션: (b / cr + r + d / cr)은 다음과 같습니다. (b + c + d) * (r / c) 즉, 비례 인자를 곱한 품질의 최소 합이 해입니다. 우리는 이미 내림차순 O (nlogn)의 r / c를 가지고 있습니다.
  • nk-1 요소에서 시작한다는 것은 마지막 k 요소가 (nk) 번째 요소의 관점에서 사용 가능한 최소 요소임을 의미합니다. 이 숫자의 최대 힙을 유지하십시오 (-min heap == max heap). 최소 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은 입력 배열의 크기입니다.

참조

Translate »