Chi phí tối thiểu để thuê K công nhân trong C ++

Giả sử có N công nhân. Mỗi công nhân có thông số chất lượng. Công nhân thứ i có phẩm chất [i] và mức lương kỳ vọng tối thiểu [i]. Bây giờ chúng tôi muốn thuê công nhân K để thành lập một nhóm có trả công. Khi chúng tôi thuê một nhóm K công nhân, chúng tôi phải trả lương cho họ theo các quy tắc sau -

Mỗi công nhân trong nhóm được trả lương phải được trả công theo tỷ lệ chất lượng của họ bằng cách so sánh với những người khác trong nhóm được trả lương.
Mọi công nhân trong nhóm được trả lương phải được trả ít nhất mức lương tối thiểu mong đợi của họ.

Chúng tôi phải tìm ra số tiền ít nhất cần thiết để tạo thành một nhóm trả phí thỏa mãn các điều kiện trên.

Vì vậy, nếu đầu vào là chất lượng =[10,22,5], lương =[70,52,30] và K =2, thì đầu ra sẽ là 105.000. Điều này là do chúng tôi sẽ trả 70 cho công nhân đầu tiên và 35 cho công nhân thứ ba.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định dữ liệu với q, w và r
n:=kích thước của chất lượng
Tạo một mảng Dữ liệu v có kích thước n
để khởi tạo i:=0, khi i
- q / v [i]:=quality [i]
- w của v [i]:=Lương [i]
- r của v [i]:=w của v [i] / q của v [i]
sắp xếp mảng v dựa trên các giá trị r
tạm thời:=0
tổng:=0
ans:=inf
Xác định một hàng đợi ưu tiên pq
để khởi tạo i:=0, khi i
- nếu kích thước của pq bằng k, thì -
  - x:=phần tử hàng đầu của pq
  - sum:=sum - x
  - xóa phần tử khỏi pq
- nếu kích thước của pq giống với k - 1, thì -
  - ans:=tối thiểu của (tổng * r của v [i]) + w của v [i] và ans
- sum:=sum + q của v [i]
- chèn q của v [i] vào pq
trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
struct Data {
   double q, w, r;
};
class Solution {
   public:
   static bool cmp(Data a, Data b) { return a.r < b.r; }
   double mincostToHireWorkers(vector<int> &quality, vector<int>
   &wage, int k) {
      int n = quality.size();
      vector<Data> v(n);
      for (int i = 0; i < n; i++) {
         v[i].q = quality[i];
         v[i].w = wage[i];
         v[i].r = v[i].w / v[i].q;
      }
      sort(v.begin(), v.end(), cmp);
      double temp = 0;
      double sum = 0;
      double ans = INT_MAX;
      priority_queue<int> pq;
      for (int i = 0; i < n; i++) {
         if (pq.size() == k) {
            double x = pq.top();
            sum -= x;
            pq.pop();
         }
         if (pq.size() == k - 1) {
            ans = min((sum * v[i].r) + v[i].w, ans);
         }
         sum += v[i].q;
         pq.push(v[i].q);
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {10,22,5}, v1 = {70,52,30};
   cout << (ob.mincostToHireWorkers(v, v1, 2));
}

Đầu vào

{10,22,5}
{70,52,30}
2

Chi phí tối thiểu để thuê K công nhân trong C ++

Ví dụ

Đầu vào

Đầu ra