leetcode 1383

问题

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers.

Example 1:

1
2
3
4
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.

Example 2:

1
2
3
4
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.

Example 3:

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

Constraints:

  • 1 <= n <= 10^5
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 10^5
  • 1 <= efficiency[i] <= 10^8
  • 1 <= k <= n

分析

我们可以直观理解为speed代表一个工程师做事的速度，也可以认为是解决问题的能力，efficiency表示其积极性。正所谓“一颗臭肉坏了整锅汤”，整个团队而言其效率总是受积极性最低的那个工程师的影响。我们在尝试组建这个团队的时候，首先要考虑的工程师考虑积极性高的工程师。首先按照efficiency从大到小的顺序将工程师进行排序，然后遍历每一个工程师。若团队中的人数小于k人，则将该工程师加入团队，团队效率变为sumSpeed*efficiency[i]。若团队中的等于k，则将目前团队中speed最小的工程师剔除团队，再加入这个刚刚遍历到的工程师计算团队效率。计算得到的团队效率更新答案的最大值。

为什么这个算法的思路是正确的？有没有漏掉的情况？

先考虑，如果这个团队一定是k个人，而不是最多是k个人是情况。这样在上述算法遍历过程中，已经模拟了从0开始的每一个子序列中选择k个人所能达到的最大的团队效率。情况没有遗漏。

再考虑，按照上述遍历，如果一个工程师加入团队之后，团队为m个人，那么有没有可能将已经在团队中的某些人踢出从而使得团队效率更高呢？没有。因为当工程师 $i$ 加入团队后，那么团队的效益将为sumSpeed*efficiency[i]，若剔除一个人，该团队中efficiency的最小值还将是efficiency[i]不会降低，而sumSpeed会由于剔除了一个人而减少。

因此，上述算法遍历了所有团队最大值的可能。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        vector<pair<int,int>> engineers(n);
        for (int i = 0; i < n; ++i) {
            engineers[i].first  = efficiency[i];
            engineers[i].second = speed[i];
        }
        sort(engineers.begin(), engineers.end(), [](
            const pair<int,int>&a, const pair<int,int> &b){return a.first>b.first;});
        
        priority_queue<int, vector<int>, greater<int>> sp;
        long long sumSpeed = 0;
        long long ans = 0;
        for (pair<int,int> &e: engineers) {
            int eff = e.first;
            int spe = e.second;
            if (sp.size() == k) {
                sumSpeed -= sp.top();
                sp.pop();
            }
            sp.push(spe);
            sumSpeed += spe;
            ans = max(ans, sumSpeed*eff);
        }
        return ans%1000000007;
    }
};