Giả sử chúng ta có hai danh sách các số có cùng độ dài được gọi là hiệu suất và chi phí. Và chúng ta cũng có một số k khác. Điều này chỉ ra rằng mỗi công nhân tôi thực hiện ở mức hiệu suất [i] và phải tốn ít nhất chi phí [i]. Chúng tôi phải tìm ra chi phí tối thiểu để thuê k nhân viên cũng như những người lao động sẽ được trả công tương xứng với hiệu suất của họ so với những nhân viên khác trong nhóm.
Vì vậy, nếu đầu vào giống như hiệu suất =[5, 3, 2] cost =[100, 5, 4] k =2, thì đầu ra sẽ là 10, vì chúng ta có thể chọn emp1 và emp2. Họ phải được trả ít nhất 5 + 4 =9 số tiền. Nhưng emp1 hoạt động tốt hơn 1,5 lần so với emp2, vì vậy anh ta phải được trả ít nhất 1,5 * 4 =6. Vì vậy, tổng cộng họ sẽ nhận được 6 + 4 =10.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=kích thước của c
-
Xác định seq mảng có kích thước n
-
điền seq với các giá trị từ 0 đến n − 1
-
sắp xếp mảng seq dựa trên các tiêu chí này (c [i] * p [j]
-
ans:=inf, psum:=0
-
xác định hàng đợi ưu tiên pq
-
để khởi tạo i:=0, khi i
-
idx:=seq [i]
-
chèn p [idx] vào pq
-
psum:=psum + p [idx]
-
nếu kích thước của pq> k, thì -
-
psum:=psum - phần tử hàng đầu của pq
-
xóa phần tử hàng đầu khỏi pq
-
-
nếu tôi> =k - 1, thì -
-
ans:=tối thiểu ans và (c [idx] / p [idx] * psum)
-
-
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
double solve(vector<int>& p, vector<int>& c, int k) {
int n = c.size();
vector<int> seq(n);
for (int i = 0; i < n; ++i)
seq[i] = i;
sort(seq.begin(), seq.end(), [&](int i, int j) { return c[i] *
p[j] < c[j] * p[i]; });
double ans = INT_MAX, psum = 0;
priority_queue<int> pq;
for (int i = 0; i < n; ++i) {
int idx = seq[i];
pq.emplace(p[idx]);
psum += p[idx];
if (pq.size() > k) {
psum −= pq.top();
pq.pop();
}
if (i >= k − 1)
ans = min(ans, (double)c[idx] / p[idx] * psum);
}
return ans;
}
int main(){
vector<int> performance = {5, 3, 2};
vector<int> costs = {100, 5, 4};
int k = 2;
cout << solve(performance, costs, k);
} Đầu vào
{5, 3, 2}, {100, 5, 4}, 2 Đầu ra
10