数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中雇佣K个工人的最低成本
假设有N个工人。每个工人都有一个质量参数。第i个工人的质量为quality[i]，最低工资期望为wage[i]。现在我们想雇佣K个工人组成一个付费小组。当我们雇佣一组K个工人时，我们必须根据以下规则支付他们：
付费小组中的每个工人应该根据他们与付费小组中其他人的质量比率来支付。
付费小组中的每个工人必须至少获得他们的最低工资期望。
我们必须找到满足上述条件的付费小组所需的最低金额。
因此，如果输入类似于quality = [10,22,5]，wage = [70,52,30]，K = 2，则输出将为105.000。这是因为我们将支付70给第一个工人，支付35给第三个工人。
为了解决这个问题，我们将遵循以下步骤：
使用q、w和r定义数据
n := quality的尺寸
创建一个大小为n的数据数组v
初始化i := 0，当i < n时，更新（i加1），执行：
v[i]的q := quality[i]
v[i]的w := wage[i]
v[i]的r := v[i]的w / v[i]的q
根据r值对数组v进行排序
temp := 0
sum := 0
ans := inf
定义一个优先级队列pq
初始化i := 0，当i < n时，更新（i加1），执行：
如果pq的大小与k相同，则：
x := pq的顶部元素
sum := sum - x
从pq中删除元素
如果pq的大小与k - 1相同，则：
ans := (sum * v[i]的r) + v[i]的w 和 ans的最小值
sum := sum + 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
更新于: 2020年6月4日
472次浏览
广告