LeetCode 1383. Maximum Performance of a Team

刺骨的言语ヽ痛彻心扉 2023-07-16 03:58 15阅读 0赞

**题目描述可以看原题**

[https://leetcode.com/problems/maximum-performance-of-a-team][https_leetcode.com_problems_maximum-performance-of-a-team]

## 思路： ##

1.  首先要将工程师编号按照效率从大到小排序。
2.  依次枚举每个工程师，维护一个大小为 k 的小根堆，存放较大的 k 个速度，同时用一个变量记录这 k 个速度的和。
3.  对于枚举到的每个工程师，如果当前堆中元素不足 k 个，则直接入堆，然后更新变量。如果已经等于了 k 个，且堆顶小于当前工程师的速度，则堆顶出堆，当前工程师的速度入堆。
4.  枚举的每一次用速度总和乘当前的效率来更新答案。

下边可以画个图来更好的理解

举个例子

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

按照效率排完序，那么六个工程师的下标是：\[4,5,1,2,3,6\], 对于k=2，我们先将效率最高的加入堆中：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70][]

那么当前**performance** 就是1\*9=9，然后放入效率第二高的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 1][]

那么当前**performance** 就是(1+5)\*min(9,7)=42，这里就会发现，结果其实就是图中直方图中的最大矩形面积，然后放入效率第三高的，很明显这个直方图的高度每次都在减少，**所以我们在替换的过程中一定是要替换效率最高并且速度值小于当前速度值**的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 2][]

那么当前**performance** 就是(2+5)\*min(5,7)=35，然后放入效率第四高的..**.（以下省略）**

到目前为止，算法的思路已经很明显了，下边放上代码，代码参考了[https://www.acwing.com/solution/LeetCode/content/10002/][https_www.acwing.com_solution_LeetCode_content_10002]

class Solution {
    public:
        int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
            const int mod = 1e9+7;
            vector<int>orders(n);
            for(int i = 0;i<n;i++)
                orders[i] = i;
            sort(orders.begin(),orders.end(),[&](int x,int y){
                return efficiency[x]>efficiency[y];
            });
            
            priority_queue<int,vector<int>,greater<int>>q;
            long long tot = 0,ans = 0;
            for(int i = 0;i<n;i++){
                if(q.size()<k){
                    q.push(speed[orders[i]]);
                    tot+=speed[orders[i]];
                }else{
                    if(q.top()<speed[orders[i]]){
                        tot -= q.top();
                        q.pop();
                        q.push(speed[orders[i]]);
                        tot += speed[orders[i]];
                    }
                }
                ans = max(ans,tot*efficiency[orders[i]]);
            }
            return ans%mod;
        }
    };

[https_leetcode.com_problems_maximum-performance-of-a-team]: https://leetcode.com/problems/maximum-performance-of-a-team
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70]: /images/20230528/011959ca2cba4e028c0a439069fcfbb9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 1]: /images/20230528/1318b20fa405403ea5bb3730d345e136.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjg1MjY1_size_16_color_FFFFFF_t_70 2]: /images/20230528/f1207dbdb1a74527a6d05a2156cfeb14.png
[https_www.acwing.com_solution_LeetCode_content_10002]: https://www.acwing.com/solution/LeetCode/content/10002/