설명

두 개의 정수 n 및 k 및 두 개의 정수 배열 speed 및 efficiency 둘 다 길이가 n입니다. n에서 1에서 n까지 번호가 매겨진 엔지니어가 있습니다. speed[i] 및 efficiency[i]는 각각 ith 엔지니어의 속도와 효율성을 나타냅니다.
k명의 엔지니어 중에서 최대 n명의 다른 엔지니어를 선택하여 최고의 성능을 발휘하는 팀을 구성합니다.

팀의 성과는 엔지니어의 속도에 엔지니어 간의 최소 효율성을 곱한 합계입니다.

이 팀의 최대 실적을 반환합니다. 답은 엄청난 숫자가 될 수 있으므로 모듈로 109 + 7 반환합니다.

예 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

예 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

예 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

제약:

1 <= k <= n <= 105

speed.length == n

efficiency.length == n

1 <= speed[i] <= 105

1 <= efficiency[i] <= 108

솔루션

솔루션 1

직관

암호

class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        int MOD = 1e9 + 7;
        vector<pair<int, int>> engineers;
        for (int i = 0; i < n; i++)
            engineers.push_back({ speed[i], efficiency[i] });
        // sort engineers by their efficiencies, from big to small
        sort(engineers.begin(), engineers.end(), [&](auto& a, auto& b) {
            return a.second > b.second;
            });
        // store their speed, the slowest is on top, could be pop
        priority_queue<int, vector<int>, greater<int>> pq;
        long speedSum = 0, res = 0;
        for (auto& [s, e] : engineers) {
            pq.push(s);
            speedSum += s;
            if (pq.size() > k) {
                // pop the slowest guy
                speedSum -= pq.top();
                pq.pop();
            }
            // note because we sort engineers by their efficiencies, so the e is the smaller one
            res = max(res, speedSum * e);
        }
        return res % MOD;
    }
};