力扣1383-最大的团队表现值

  |  

摘要: 双指标规划问题,TopK 问题变种

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们看一个贪心中的双指标规划问题。可以视为 TopK 问题的变种。这是第 180 场周赛 D 题。

$1 题目

1383. 最大的团队表现值

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

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

1
2
3
4
5
6
1 <= n <= 10^5
speed.length == n
efficiency.length == n
1 <= speed[i] <= 10^5
1 <= efficiency[i] <= 10^8
1 <= k <= n

示例 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

$2 题解

算法:topK 问题

候选数据是工程师,一个工程师有 efficiency 和 speed 两种属性:

1
2
3
4
5
struct Engineer
{
int speed, efficiency;
Engineer(int s, int e):speed(s),efficiency(e){}
};

当固定 efficiency 时候,目标是从满足条件的 speed 中选择最大的 k 个,其中只要工程师的 efficiency 不小于当前枚举的 efficiency 时即满足条件。

当 efficiency 从大往小枚举时,可选的工程师越来越多,在越来越多的数据中选择前 K 个,这是数据流的前 k 大问题。力扣中有具体题目 703. 数据流中的第K大元素

算法流程是现将所有工程师排序,标准是是当 efficiency 相等的时候,speed 越大的排前面,否则 efficiency 大的排前面。

1
2
3
4
5
6
7
8
9
struct Cmp 
{
bool operator()(const Engineer& engineer1, const Engineer& engineer2)
{
if(engineer1.efficiency == engineer2.efficiency)
return engineer1.speed > engineer2.speed;
return engineer1.efficiency > engineer2.efficiency;
}
};

排序后得到候选工程师,然后从前往后枚举,释放该候选工程师,更新 topk 的结果。

在最小堆中维护最大的 k 个满足条件的 speed。从前往后枚举排序后的工程师对应的 speed。更新答案。

因为是最多选择 k 个不是正好选 k 个,所以堆中元素小于 k 个的时候也要更新答案。

题目 857. 雇佣 K 名工人的最低成本,与本题思路完全相同,在本题中枚举性价比的指标,枚举到 x 时,性价比小于 x 的是满足的,因此随着 x 变大,满足的人越来越多,从这越来越多的人中选某个指标最优的 k 个。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
vector<Engineer> engineers;
for(int i = 0; i < n; ++i)
engineers.push_back(Engineer(speed[i], efficiency[i]));
sort(engineers.begin(), engineers.end(), Cmp());
ll result = 0;
ll sum = 0;
int min_efficiency = INT_MAX;
priority_queue<int, vector<int>, greater<int> > pq;
for(int i = 0; i < n; ++i)
{
min_efficiency = min(min_efficiency, engineers[i].efficiency);
pq.push(engineers[i].speed);
sum += engineers[i].speed;
if((int)pq.size() > k)
{
sum -= pq.top();
pq.pop();
}
result = max(result, sum * min_efficiency);
}
return result % MOD;
}

private:
using ll = long long;
const int MOD = 1e9 + 7;

struct Engineer
{
int speed, efficiency;
Engineer(int s, int e):speed(s),efficiency(e){}
};

struct Cmp
{
bool operator()(const Engineer& engineer1, const Engineer& engineer2)
{
if(engineer1.efficiency == engineer2.efficiency)
return engineer1.speed > engineer2.speed;
return engineer1.efficiency > engineer2.efficiency;
}
};
};

Share