class Solution {
public:
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
}
};
1383. 最大的团队表现值
公司有编号为 1 到 n 的 n 个工程师，给你两个数组 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 解释： 我们选择工程师 2（speed=10 且 efficiency=4）和工程师 5（speed=5 且 efficiency=7）。他们的团队表现值为 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^5speed.length == nefficiency.length == n1 <= speed[i] <= 10^51 <= efficiency[i] <= 10^81 <= k <= n原站题解
php 解法, 执行用时: 172 ms, 内存消耗: 67.4 MB, 提交时间: 2023-09-25 17:25:26
class Solution {
/**
* @param Integer $n
* @param Integer[] $speed
* @param Integer[] $efficiency
* @param Integer $k
* @return Integer
*/
function maxPerformance($n, $speed, $efficiency, $k) {
$map = [];
for ($i = 0; $i < $n; ++$i) {
$map[] = [$efficiency[$i], $speed[$i]];
}
rsort($map);
$hp = new \SplMinHeap;
$sum = $ans = 0;
foreach ($map as $m) {
$ans = max($ans, $m[0] * ($m[1] + $sum));
$hp->insert($m[1]);
$sum += $m[1];
if ($hp->count() == $k) {
$sum -= $hp->top();
$hp->extract();
}
}
return $ans % (1e9 + 7);
}
}
rust 解法, 执行用时: 804 ms, 内存消耗: 4 MB, 提交时间: 2023-09-25 17:25:02
use std::cmp::Reverse;
use std::collections::BinaryHeap;
impl Solution {
const M: u64 = 1e9 as u64 + 7;
pub fn max_performance(n: i32, speed: Vec<i32>, efficiency: Vec<i32>, k: i32) -> i32 {
let mut engineers: Vec<Engineer> = speed.iter()
.zip(efficiency.iter())
.map(|(s, e)| { Engineer { speed: *s, efficiency: *e } })
.collect();
engineers.sort_by_key(|e| Reverse(e.efficiency));
let mut max_performance = 0;
let mut min_heap = BinaryHeap::new();
for engineer in engineers.iter() {
min_heap.push(Reverse(engineer.speed));
if min_heap.len() > k as usize {
min_heap.pop();
}
let speeds: u64 = min_heap.iter().map(|Reverse(i)| *i as u64).sum();
let perf: u64 = speeds as u64 * engineer.efficiency as u64;
max_performance = max_performance.max(perf)
}
(max_performance % Solution::M) as i32
}
}
struct Engineer {
speed: i32,
efficiency: i32,
}
python3 解法, 执行用时: 296 ms, 内存消耗: 46.4 MB, 提交时间: 2023-09-25 17:24:07
import heapq
class Solution:
class Staff:
def __init__(self, s, e):
self.s = s
self.e = e
def __lt__(self, that):
return self.s < that.s
def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
v = list()
for i in range(n):
v.append(Solution.Staff(speed[i], efficiency[i]))
v.sort(key=lambda x: -x.e)
q = list()
ans, total = 0, 0
for i in range(n):
minE, totalS = v[i].e, total + v[i].s
ans = max(ans, minE * totalS)
heapq.heappush(q, v[i])
total += v[i].s
if len(q) == k:
item = heapq.heappop(q)
total -= item.s
return ans % (10**9 + 7)
java 解法, 执行用时: 41 ms, 内存消耗: 54.8 MB, 提交时间: 2023-09-25 17:23:02
class Solution {
class Staff {
int s, e;
public Staff(int s, int e) {
this.s = s;
this.e = e;
}
}
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
final int MODULO = 1000000007;
List<Staff> list = new ArrayList<Staff>();
PriorityQueue<Staff> queue = new PriorityQueue<Staff>(new Comparator<Staff>() {
public int compare(Staff staff1, Staff staff2) {
return staff1.s - staff2.s;
}
});
for (int i = 0; i < n; ++i) {
list.add(new Staff(speed[i], efficiency[i]));
}
Collections.sort(list, new Comparator<Staff>() {
public int compare(Staff staff1, Staff staff2) {
return staff2.e - staff1.e;
}
});
long ans = 0, sum = 0;
for (int i = 0; i < n; ++i) {
Staff staff = list.get(i);
long minE = staff.e;
long sumS = sum + staff.s;
ans = Math.max(ans, sumS * minE);
queue.offer(staff);
sum += staff.s;
if (queue.size() == k) {
sum -= queue.poll().s;
}
}
return (int) (ans % MODULO);
}
}
cpp 解法, 执行用时: 60 ms, 内存消耗: 37.4 MB, 提交时间: 2023-09-25 17:22:21
class Solution {
public:
using LL = long long;
struct Staff {
int s, e;
bool operator < (const Staff& rhs) const {
return s > rhs.s;
}
};
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
vector<Staff> v;
priority_queue<Staff> q;
for (int i = 0; i < n; ++i) {
v.push_back({speed[i], efficiency[i]});
}
sort(v.begin(), v.end(), [] (const Staff& u, const Staff& v) { return u.e > v.e; });
LL ans = 0, sum = 0;
for (int i = 0; i < n; ++i) {
LL minE = v[i].e;
LL sumS = sum + v[i].s;
ans = max(ans, sumS * minE);
q.push(v[i]);
sum += v[i].s;
if (q.size() == k) {
sum -= q.top().s;
q.pop();
}
}
return ans % (int(1E9) + 7);
}
};
golang 解法, 执行用时: 68 ms, 内存消耗: 10 MB, 提交时间: 2023-09-25 17:21:27
/**
* 小根堆
* 先建立下标数组，然后按效率从大到小对下标数组进行排序排序 遍历下标数组，
* 并建立一个存储速度值的最小堆，维护最小堆的大小不超过k 遍历过程中计算团队表现值
*/
func maxPerformance(n int, speed []int, efficiency []int, k int) int {
indexes := make([]int, n) // 下标数组
for i := range indexes {
indexes[i] = i
}
sort.Slice(indexes, func(i, j int) bool {
return efficiency[indexes[i]] > efficiency[indexes[j]]
}) // 按效率从大到小对下标数组排序
ph := speedHeap{}
heap.Init(&ph)
var speedSum int
var max int64
for _, index := range indexes {
if ph.Len() == k {
speedSum -= heap.Pop(&ph).(int)
}
speedSum += speed[index]
heap.Push(&ph, speed[index])
max = Max(max, int64(speedSum)*int64(efficiency[index]))
}
return int(max % (1e9 + 7))
}
type speedHeap []int
func (h speedHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h speedHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h speedHeap) Len() int { return len(h) }
func (h *speedHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *speedHeap) Pop() interface{} { res := (*h)[len(*h)-1]; *h = (*h)[:h.Len()-1]; return res}
func Max(a, b int64) int64 { if a > b { return a }; return b }