企业网站提交,app的好处与弊端,手机可以制作app软件吗,毕业设计动漫网页设计1. 题目
公司有编号为 1 到 n 的 n 个工程师#xff0c;给你两个数组 speed 和 efficiency #xff0c;其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。 请你返回由最多 k 个工程师组成的 最大团队表现值 #xff0c;由于答案可能很大给你两个数组 speed 和 efficiency 其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。 请你返回由最多 k 个工程师组成的 最大团队表现值 由于答案可能很大请你返回结果对 10^9 7 取余后的结果。
团队表现值 的定义为一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。
示例 1
输入n 6, speed [2,10,3,1,5,8], efficiency [5,4,3,9,7,2], k 2
输出60
解释
我们选择工程师 2speed10 且 efficiency4和工程师 5speed5 且 efficiency7。
他们的团队表现值为 performance (10 5) * min(4, 7) 60 。示例 2
输入n 6, speed [2,10,3,1,5,8], efficiency [5,4,3,9,7,2], k 3
输出68
解释
此示例与第一个示例相同除了 k 3 。我们可以选择工程师 1
工程师 2 和工程师 5 得到最大的团队表现值。
表现值为 performance (2 10 5) * min(5, 4, 7) 68 。示例 3
输入n 6, speed [2,10,3,1,5,8], efficiency [5,4,3,9,7,2], k 4
输出72提示
1 n 10^5
speed.length n
efficiency.length n
1 speed[i] 10^5
1 efficiency[i] 10^8
1 k n来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-performance-of-a-team 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
参考大佬的思路Ikaruga按照效率 ηi\eta_iηi 降序排序遍历每个人最大团队值为 minηi∗∑speed\min \eta_i*\sum speedminηi∗∑speedηi\eta_iηi 是下降的那么效率高于 ηi\eta_iηi 的人在人数少于 kkk 的时候全部加入使得第二项最大当人数超过 kkk 了在 ηi\eta_iηi 下比其效率高的人中我要选出 speedspeedspeed 最大的 kkk 人这样每个 ηi\eta_iηi 作为第一项的情况 都遍历过了且每次遍历的时候挑出来的人也都是 speedspeedspeed 最快的
class Solution {
public:int maxPerformance(int n, vectorint speed, vectorint efficiency, int k) {vectorvectorint people;int i, e, s;long long maxPerf 0, speedsum 0;for(i 0; i speed.size(); i){people.push_back({efficiency[i], speed[i]});}sort(people.rbegin(), people.rend());//按照效率从大到小排序priority_queueint, vectorint,greaterint q;//小顶堆for(i 0; i speed.size(); i){e people[i][0];//效率speedsum people[i][1];//速度和k--;//人数-1q.push(people[i][1]);//速度队列堆顶最小if(k 0)//人超过k人了{speedsum - q.top();//速度小的删除q.pop();}maxPerf max(maxPerf, e*speedsum);//这里不要取模}return maxPerf%1000000007;}
};
