K işçilərini işə götürmək üçün minimum xərc

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur google
YığınBaxılıb 34
LinkedInBuferRedditTumblr

K işçilərini işə götürmək üçün minimum xərclə, ödənişli bir qrup yaratmaq üçün tam olaraq k işçi cəlb etmək istədiyimiz N işçini verdik. I-ci işçi keyfiyyət [i] və minimum əmək haqqı gözləmə maaşına [i] malikdir.

Ödəniş onlara aşağıdakı qaydalara əsasən veriləcəkdir:

  1. Ödənişli qrupdakı hər bir işçiyə, ödənişli qrupdakı digər işçilərə nisbətən keyfiyyət nisbətində maaş verilməlidir.
  2. Ödənişli qrupdakı hər bir işçiyə ən azı minimum əmək haqqı gözləntiləri ödənilməlidir.

misal

Input: keyfiyyət = [50, 30, 10, 60, 70], əmək haqqı = [100, 120, 130, 90, 140], K = 3

Çıxış: 360

K İşçiləri Kirayəyə götürmək üçün Minimum Maliyyət üçün əsas məqamlar

Deyək ki, keyfiyyət = [a, b, c, d] və əmək haqqı = [p, q, r, s]

  • Birinci elementə nisbətən keyfiyyətin effektiv nisbəti belə olacaqdır: [1, b / a, c / a, d / a]
  • Effektiv əmək haqqı: [p, pb / a, pc / a, pd / a]
  • Təmin etmək minimum əmək haqqı j elementi nisbətdə hesab edildikdə ith elementini seçərək ödənişli bir işçi qrupu yaratmaq: B [i] <= (A [i] / A [j]) * B [j] == B [i] / A [i] <= B [j] / A [j] yəni keyfiyyət / min əmək haqqı nisbətinin şərt nisbətini təmin etmək üçün azalan sırada yerləşdirilməli və bütün sonrakı nisbət jth işçi hesab edilərkən minimum əmək haqqı şərtini avtomatik olaraq təmin edəcəkdir. bu element.
  • Üçün optimal həll: demək (b / cr + r + d / cr) yazının ekvivalentidir: (b + c + d) * (r / c), yəni nisbət əmsalına vurulan keyfiyyətlərin minimum cəmi həlldir. Artıq r / c azalan O (nlogn) sırasına sahibik.
  • Nk-1 elementindən başlayaraq, son k elementlərinin (nk) th elementi baxımından minimum mövcud elementlər olması deməkdir. Bu rəqəmlərdən maksimum yığını qoruyun (- min yığın == maksimum yığın). Maksimum min k elementdən kiçik bir rəqəm gördüyümüz kimi: yalnız maksimumu götürüb yeni elementi daxil edirik.
  • Yeni kiçik element aşkarlandıqdan sonra: yığın yenilənir və yeni potensial minimum məbləğ yoxlanılır.

K işçilərini işə götürmək üçün minimum xərc üçün tətbiqetmə

C ++ Proqramı

#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 Proqramı

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 işçilərini işə götürmək üçün minimum xərc üçün mürəkkəblik analizi

Zaman mürəkkəbliyi

O (NlogN) Yığın / prioritet növbəyə əlavə etmək vaxt alır və biz hamısını dolaşırıq array bundan sonra ümumi zaman mürəkkəbliyi O olacaqdır (NlogN)

Kosmik Mürəkkəblik

O (N) burada N giriş massivinin ölçüsüdür.

References

LinkedInBuferRedditTumblr
Translate »