LeetCode 1383 - 最大的团队表现值

题目描述

公司有编号为 1 到 n 的 n 个工程师，给你两个数组 speed 和 efficiency ，其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的最大团队表现值，由于答案可能很大，请你返回结果对 10^9 + 7 取余后的结果。

团队表现值的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。

选择合适的解题思路

这题挺难的。因为计算方式是 sum(speed) * min(efficiency)，所以并不好直接排序，有的人效率低但是速度大，而且效率不是累加是取最小值，这使得排序策略更加复杂

也就是说状态方程不好写，所以就顺利成章想到遍历，但是这个遍历的角度挺值得学习：
1. 假设我们一定要选择某个工程师（假设叫小白）
2. 我们遍历到小白，假设他是最后选择的人中效率最低的
3. 那么我们应该如何选择其他人？

答案就变得简单了：
- 先筛选出效率比小白大的人
- 此时这些人中虽然效率比他大，但最后都是统一乘以小白的效率
- 所以我们只要从中选择速度最大的 K-1 个人即可

你可能会担心：小白虽然在最终的 K 人中，但并不是效率最低的怎么办？这个没有关系，假设效率最低的人是小庄，那么我们会在遍历到小庄的时候选择 K-1 人时将小白选到。

选择合适的实现方法

那么就开始遍历呗，需要做两件事情：筛选出效率比当前工程师大的人、从里面按照速度选择 K-1 人。如何做？

实现方法也非常值得学习，按照效率从大到小排序，这样遍历到 i 时，那么之前的都是筛选后的人！此外，这种处理方式也帮助了我们按照速度选择人选：因为每次遍历到 i 时，我们肯定只在 0 ~ i-1 中选择速度大的人，这是一个顺序的过程，所以我们始终记录前面速度最大的 K 个人就行了！

// 根据效率值从大到小排序
sorted_by_effeciency(Persons);

// 始终维护一个数据结构，用来表示前面 K-1 个最大速度
PriorityQueue<Long> q = new PriorityQueue<Long>();

int speed_sum = 0;
for(int i = 0; i < K-1; ++i) { 
    q.add(Persons[i].speed); 
    speed_sum += Persons[i].speed;
}

int ans = 0;
for(int i = K; i < N; ++i) {
    // 从中删除一个
    speed_sum -= q.poll();

    // 一定选择当前的 ith Person
    speed_sum += Persons[i].speed;
    q.add(Persons[i].speed);

    ans = Math.max(ans, speed_sum * pairs[i].effeciency);
}

Comments