Maximum Performance of a Team trong C++

Có n kỹ sư, speed[i] và efficiency[i]. Chọn tối đa k người. Performance = (tổng speed) × (min efficiency trong nhóm). Tối đa hóa performance modulo 10^9+7.

Ví dụ: n=6, speed=[1,5,8,2,10,3], efficiency=[9,7,2,5,4,3], k=2 → chọn speed 10 (eff 4) và 5 (eff 7) → (10+5)*min(4,7)=60.

Giải thuật (Sắp xếp + Priority Queue)

1. Ghép cặp (efficiency, speed), sắp xếp giảm dần theo efficiency.
2. Duyệt theo efficiency giảm dần: efficiency hiện tại là min efficiency của nhóm.
3. Dùng min-heap lưu speed của k người đã chọn. Giữ tổng speed lớn nhất.
4. Cập nhật ans = max(ans, sumSpeed * currentEfficiency).

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        vector<pair<int,int>> engineers;
        for (int i = 0; i < n; i++)
            engineers.emplace_back(efficiency[i], speed[i]);
        sort(engineers.rbegin(), engineers.rend()); // giảm dần efficiency
        
        priority_queue<int, vector<int>, greater<int>> pq; // min-heap speed
        long long sumSpeed = 0, ans = 0;
        const long long MOD = 1e9 + 7;
        
        for (auto& [eff, spd] : engineers) {
            if (pq.size() == k) {
                sumSpeed -= pq.top();
                pq.pop();
            }
            sumSpeed += spd;
            pq.push(spd);
            ans = max(ans, sumSpeed * eff);
        }
        return ans % MOD;
    }
};

int main() {
    Solution ob;
    vector<int> s = {1,5,8,2,10,3};
    vector<int> e = {9,7,2,5,4,3};
    cout << ob.maxPerformance(6, s, e, 2); // 60
    return 0;
}

Đầu vào / Đầu ra

Input: 6, {1,5,8,2,10,3}, {9,7,2,5,4,3}, 2
Output: 60