雇用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的数据v的数组

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• v [i]的q：=质量[i]

• v [i]的w：=工资[i]

• v [i]的r：= v [i]的w / v [i]的q

• 根据r值对数组v排序

• 温度：= 0

• 和：= 0

• ans：= inf

• 定义一个优先级队列pq

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• ans：=（v [i]的和（sum * r）+ v [i]的w和ans的最小值

• x：= pq的顶部元素

• 总和：=总和-x

• 从pq中删除元素

• 如果pq的大小与k相同，则-

• 如果pq的大小与k-1相同，则-

• 总和：=总和+ v [i]的q

• 将v [i]的q插入pq

• 返回ans

让我们看下面的实现以更好地理解-

示例

#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

输出结果

105