Chi phí thuê K công nhân tối thiểu trong C++

Có N công nhân, mỗi người có quality[i] và wage[i] (lương tối thiểu). Thuê K người, trả lương tỷ lệ với quality, và mỗi người phải được trả ≥ wage[i]. Tìm tổng lương nhỏ nhất.

Ví dụ: quality=[10,22,5], wage=[70,52,30], K=2 → 105.0 (trả 70 cho người 1, 35 cho người 3).

Giải thuật

1. Tính tỷ lệ r[i] = wage[i]/quality[i]. Sắp xếp công nhân theo r tăng dần.
2. Duyệt i từ 0 đến n-1, coi công nhân i là người có tỷ lệ cao nhất trong nhóm (định ra mức lương cơ sở).
3. Dùng max-heap lưu quality của K-1 công nhân có quality nhỏ nhất trong các công nhân trước i.
4. Nếu heap size == K: tính total_quality = sum_heap + quality[i], chi phí = total_quality * r[i]. Cập nhật ans.
5. Push quality[i] vào heap, nếu size > K-1 thì pop max quality.

Ví dụ mã C++

#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 sum = 0, ans = INT_MAX;
        priority_queue<int> pq;
        for (int i = 0; i < n; i++) {
            if (pq.size() == k) { sum -= pq.top(); 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;
    }
};
int main(){
    Solution ob;
    vector<int> v = {10,22,5}, v1 = {70,52,30};
    cout << (ob.mincostToHireWorkers(v, v1, 2));
}

Đầu vào

{10,22,5} {70,52,30} 2

Đầu ra

105