# Halo

A magic place for coding

0%

## Problem

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively.

Choose at most k different engineers out of the n engineers to form a team with the maximum performance.

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

Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 109 + 7.

Example 1:

Example 2:

Example 3:

Constraints:

• 1 <= k <= n <= 105
• speed.length == n
• efficiency.length == n
• 1 <= speed[i] <= 105
• 1 <= efficiency[i] <= 108

## Analysis

题目的通过两个数组，给出了每个工人的速度和效率，定义整个团队的performance是最小的效率乘以速度之和。要求我们从中选出k个成员，找到能够最大化的performance。首先，这里的关键应该是最小的效率，因为每个人的速度都要乘以它，所以我们优先考虑效率。我们先根据效率从大到小排序，然后把每一个成员的速度加起来，全局维护一个极大值。

然后，问题就转化为如果人数超过了k个人怎么办？因为效率是从大到小遍历的，所以当处理到第i个工人时，肯定是以第i个工人的效率为最低效率，关键是速度。因为我们要的是速度之和最大，很自然地我们就需要剔除掉速度最小的一个工人了，所以我们需要用一个最小堆去记录。当超过k个人之后，剔除掉速度最小的即可。

无。

## Summary

这道题难度中等，面对这种有数量限制的题目，一般采用的是滑动窗口（连续）或者堆（非连续）。这道题目的分享到这里，感谢你的支持！

Welcome to my other publishing channels