LeetCode 5359. 最大的团队表现值(贪心)
- 2020 年 3 月 17 日
- 筆記
题目链接:https://leetcode-cn.com/problems/maximum-performance-of-a-team/
首先我们对n个人进行排序,优先效率从大到小,然后我们维护一个堆(set或者priority_queue都可以),堆中每次维护k个值,也就是我们所要选择的k个人。那么对于这前k个人来说的团队表现值就是sum*v[k-1].efficiency,那么对于下一个人来说,他是第k+1个将他加入到堆中,然后我们删去堆中speed最小的人,由于efficiency是从大到小排序,那么删除的这个人的efficiency一定是大于这个第k+1个人的,所以不需要去考虑删除的efficiency,那么此时的团队表现值就是sum*v[k].efficiency,就这样遍历到最后维护一个最大团队表现值就好了。
AC代码:
class Solution { public: const int mod = 1e9 + 7; vector<pair<int,int> > v; typedef pair<int,int> p; multiset<int> s; int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) { for(int i=0;i<n;i++){ v.push_back(p(speed[i], efficiency[i])); } sort(v.begin(), v.end(), [](const pair<int,int> a, const pair<int,int> b){ if(a.second == b.second) return a.first > b.first; return a.second > b.second; }); long long sum = 0; long long ans = 0; for(int i=0;i<n;i++){ sum += v[i].first; s.insert(v[i].first); if(s.size() > k){ sum -= *s.begin(); s.erase(s.begin()); } ans = max(ans, sum * v[i].second); } return ans % mod; } };