資料結構
網路
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次瀏覽
廣告