雇用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