C++에서 K 작업자를 고용하기 위한 최소 비용

<시간/>

N명의 작업자가 있다고 가정합니다. 각 작업자에는 품질 매개변수가 있습니다. i번째 근로자는 자질[i]과 최저임금 기대임금[i]을 갖는다. 이제 K 직원을 고용하여 유료 그룹을 구성하려고 합니다. K 직원 그룹을 고용할 때 다음 규칙에 따라 급여를 지급해야 합니다. -

유급 그룹의 각 근로자는 유급 그룹의 다른 직원과 비교하여 품질의 비율로 급여를 받아야 합니다.
유급 그룹의 모든 근로자는 최소 기대 임금 이상을 받아야 합니다.

위의 조건을 만족하는 유료 그룹을 구성하는 데 필요한 최소 금액을 찾아야 합니다.

따라서 입력이 품질 =[10,22,5], 임금 =[70,52,30] 및 K =2와 같으면 출력은 105.000이 됩니다. 첫 번째 작업자에게 70, 세 번째 작업자에게 35를 지불하기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

q, w 및 r을 사용하여 데이터 정의
n :=품질의 크기
n
크기의 Data v 배열을 만듭니다.
initialize i :=0의 경우, i
- v[i]의 q :=품질[i]
- w의 v[i] :=임금[i]
- v[i]의 r :=v[i]의 w /v[i]의 q
r 값을 기반으로 배열 v 정렬
온도 :=0
합계 :=0
ans :=inf
하나의 우선순위 큐 pq 정의
initialize i :=0의 경우, i
- pq의 크기가 k와 같으면 -
  - x :=pq의 최상위 요소
  - 합계 :=합계 - x
  - pq에서 요소 삭제
- pq의 크기가 k - 1과 같으면 -
  - ans :=(sum * r of v[i]) + w of v[i] 및 ans
    의 최소값
- 합계 :=합계 + v[i]의 q
- v[i]의 q를 pq에 삽입
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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));
}

입력

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