Giả sử ta có hai danh sách số cùng độ dài: performance và costs. Còn có số k. Chúng cho biết nhân viên i làm việc ở mức performance[i] và chi phí tối thiểu costs[i]. Ta phải tìm chi phí tối thiểu để tuyển k nhân viên, với điều kiện nhân viên được trả lương tỷ lệ với hiệu suất so với các nhân viên khác trong nhóm.
Ví dụ: performance = [5, 3, 2], costs = [100, 5, 4], k = 2, đầu ra = 10. Chọn emp1 và emp2. Phải trả ít nhất 5+4=9. Nhưng emp1 hiệu suất 1.5 lần emp2, nên emp1 phải trả ít nhất 1.5*4=6. Tổng = 6+4=10.
Để giải quyết, ta làm theo các bước:
- n := kích thước c.
- Định nghĩa mảng seq kích thước n, điền 0..n-1.
- Sắp xếp seq theo tiêu chí (c[i] * p[j] < c[j] * p[i]).
- ans := inf, psum := 0.
- Định nghĩa hàng đợi ưu tiên pq.
- for i := 0; i < n; ++i:
- idx := seq[i].
- Chèn p[idx] vào pq.
- psum += p[idx].
- Nếu pq.size() > k: psum -= pq.top(); pq.pop().
- Nếu i >= k-1: ans = min(ans, (double)c[idx] / p[idx] * psum).
- Trả về ans.
Xem triển khai dưới đây:
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